蓝桥发现环

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; }