经典算法 输出在环上的点

输出在环上的点

问题描述

给你一个无向图，已知这个图上有一些环，请输出所有环路上的节点编号。

输入描述

第一行包含一个整数 N。

后面N行每行两个整数 a,b，表示 a和 b 之间有一条边相连。

你可以假设节点编号是在1-100000范围内，并且你可以假设不需要对节点做离散化处理。

输出描述

按字典顺序输出环路上的节点编号。

示例输入

5
1 2
3 1
2 4
2 5
5 3

示例输出

1 2 3 5

c++代码

#include<bits/stdc++.h>
#include<stdio.h>using namespace std;int a, b, x;int main() {int N;scanf("%d", &N);vector<vector<int>> arr(N + 1);vector<int> d(N + 1, 0), ans;for (int i = 0; i < N; i++) {scanf("%d %d", &a, &b);arr[a].push_back(b), arr[b].push_back(a), d[a]++, d[b]++;}queue<int> qu;for (int i = 1; i <= N; i++) {if (d[i] == 1) qu.push(i);}while(!qu.empty()) {x = qu.front(), qu.pop(), d[x]--;for (int y : arr[x]) {d[y]--;if (d[y] == 1) qu.push(y);}}for (int i = 1; i <= N; i++) {if (d[i] > 1) ans.push_back(i);}sort(ans.begin(), ans.end());for (int i = 0; i < ans.size(); i++) {printf("%d", ans[i]);if (i != ans.size() - 1) printf(" ");}return 0;
}//by wqs

题目解析

判断一个图是否有环，依次删除度为 1 的点以及与其相连的边，这样可以把所有不成环的链上点依次删除，最后也无法被删除的点集就是题目要求的答案，按照编号从小到大输出即可。

具体步骤

1. 统计所有点的入度；
2. 创建一个队列维护所有入度为 1 的点，将所有度等于 1 的节点加入队列。（本题中没有独立的节点，所以不用考虑度为 0 的情况）；
3. 当队列不为空时，弹出队首元素，把与队首元素相邻的节点入度减 1，如果相邻节点度数变为 1，则将相邻节点加入队列；
4. 循环结束后，从小到大判断每个结点的入度，若入度大于 1，则说明该节点在环内，输出该节点。