具体实现用树形结构，如果a,b所在组相同，则a,b有相同的根结点。合并两组时即让一组的根向另一组相连。
为了避免树形结构下发生退化的情况，在并查集中可以如下操作：
此外还可以路径压缩，即把每个结点都直接与其根结点相连，树的高度为2.在查询过程中查询过程中递归的所有节点都直接指向根结点。
此时为方便起见，即使树的高度改变，我们也不修改rank的值(rank只是在合并时决定谁向谁连根)。
具体见下实现代码。
若(u,v)之间有边，则将u,v放入同一组。如果在放入u,v之前已经在同一组，即从u可以到v，那么加入边(u,v)后就形成了一个环。
以u或v作为环的起点，用dfs方法遍历每个顶点相邻的顶点，看最后是否回到了起点，如果沿某一路径回到起点，则说明这些
顶点在这个环内。
#include<cstdio> #include<algorithm> #include<vector> using namespace std; const int Max_N = 100000; //输入 int n; int s;//环的起点 vector<int> G[Max_N+1];//图 vector<int> V;//记录环 bool visited[Max_N+1];//结点是否访问过(避免重复访问) int par[Max_N+1];//并查集 int rank[Max_N+1];//并查集高度 //初始化并查集 void init(int n) { for(int i=1; i<=n; i++){//刚开始互相没有边相连 par[i] = i; } } //找下标x的根 int find(int x) { return x==par[x] ? x:par[x] = find(par[x]);//par[x] = find(par[x])即路径压缩 } //合并 void unite(int x,int y) { x = find(x); y=find(y);//先找到他们的根 if( x==y ){ return;//同根 直接返回 } if( rank[x]<rank[y] ){ par[x] = y;//将x所在的树合并在y下 } else { par[y] = x; if( rank[x]==rank[y] ){//如果高度相同 更新rank[x] rank[x]++; } } } //x,y是否在同一组 即是否同根 bool same(int x,int y) { return find(x)==find(y); } //dfs bool dfs(int u) { if( visited[u] )//如果最后访问的结点回到起点,则在环内 { if( u==s ) { return true; } return false;//否则不在环内 } visited[u] = true;//u已经访问过 for(int i=0; i<G[u].size(); i++)//遍历顶点 u 的相邻边 { int v = G[u][i];//下一个顶点 if( dfs(v) )//在环内 { V.push_back(v); return true; } } return false;//遍历所有边都不在环内 } void solve() { dfs(s); sort(V.begin(),V.end()); vector<int>::iterator it; for( it=V.begin(); it!=V.end(); it++) { printf("%d ",*it); } printf("\n"); } int main() { scanf("%d",&n); init(n); while( n-- ) { int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); if( same(u,v) ){//u,v已经有路径了 s = u;//起点下标 } unite(u,v); } solve(); return 0; }
原文：https://www.cnblogs.com/w-like-code/p/12934398.html