0发现环 - 蓝桥云课
找到环
不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了BUG。
为了恢复正常传输，小明需要找到所有在环路上的电脑，你能帮助他吗？
输入描述
输入范围：
- 第一行包含一个整数 N。
- 以下 N 行每行两个整数 a,b，表示 a 和 b 之间有一条数据链接相连。
- 其中，1≤N≤105，1≤a,b≤N。
- 输入保证合法。
输出描述
按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。
输入输出样例
示例：
输入：
5
1 2
3 1
2 4
2 5
5 3输出：
1 2 3 5运行限制
- 最大运行时间：1s
- 最大运行内存：256M
总通过次数：3106 | 总提交次数：3881 | 通过率：80%
难度：困难 标签：2017，拓扑排序，并查集，国赛，DFS
思路：
图中只有一个环。
因为环的度一定>=2,所以我们可以用拓扑排序维护度为1的节点。剩下的节点>=2就是环的节点
代码如下：
#include <iostream>
#include <queue>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int n,tot;
int du[N];
struct Edge{int to,next;
}e[4*N];
int head[N];
void add(int u,int v)
{++tot;e[tot].next = head[u];e[tot].to = v;head[u] = tot;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);queue <int> r;cin >> n;for(int i = 1 ; i <= n ; i++)head[i] = -1;for(int i = 1 ; i <= n ; i++){int u,v;cin >> u >> v;add(u,v);add(v,u);du[u]++;du[v]++;}for(int i = 1 ; i <= n ; i++){if(du[i] == 1){r.push(i);}}while(!r.empty()){int pos = r.front();du[pos]--;r.pop();int u = head[pos];while(u != -1){int to = e[u].to;if(du[to] > 0){du[to]--;if(du[to] == 1){r.push(to);}}u = e[u].next;} } for(int i = 1 ; i <= n ; i++){if(du[i] > 1)cout << i << " ";}return 0;
}
