首先我写的代码应该是有问题的，可能连数据都没输入完答案就出来了，但确实是AC了(大概数据里都是最后一条边输入才会生成环)，代码先放这里，下次优化
基本思路：先并查集判断当一条边的两个顶点的祖先一样，说明这两个点是环的一部分，从一个点出发dfs到另一个顶点即可
还有一个思路是在网上看的：拓扑排序每次删掉度为1的点，一直删一直删，剩下的就是环了
#include<iostream> #include<stack> #include<vector> #include<algorithm> #include<cstdio> using namespace std; const int maxn = 100010; int per[maxn]; int n; vector<int> e[maxn]; stack<int>res; int vis[maxn]; int a[maxn]; int find(int x){ if (x == per[x]) return x; return per[x] = find(per[x]); } void join(int x, int y){ int fx = find(x), fy = find(y); if (fx != fy) per[fx] = fy; } void print(){ int t = 0; while (!res.empty()){ a[t++] = res.top(); res.pop(); } sort(a,a+t); for (int i = 0; i < t-1; i++){ cout << a[i] << ‘ ‘; } cout << a[t - 1] << endl; } void dfs(int start,int end){ res.push(start); vis[start] = 1; if (start == end){ print(); exit(0); } for (int i = 0; i < e[start].size(); i++){ if (e[e[start][i]].size() >= 2 && vis[e[start][i]] == 0) dfs(e[start][i], end); } res.pop(); vis[start] = 0; } int main() { int a, b; cin >> n; for (int i = 0; i <= n; i++){ per[i] = i; vis[i] = 0; } for (int i = 1; i <= n; i++){ scanf("%d%d",&a,&b); e[a].push_back(b); e[b].push_back(a); int fa = find(a), fb = find(b); if (fa != fb) per[fa] = fb; else dfs(a,b); } return 0; }
原文：https://www.cnblogs.com/looeyWei/p/10462634.html
