在学习krustra的算法时遇到了一个查找是否存在环路的算法，代码如下：
int find(int *parent,int f) { while(parent[f]>0) { f=parent[f]; } return f; } for(int i=0;i<k;i++) { int temp=0; int a,b; a=find(parent,Edge[i].begin); b=find(parent,Edge[i].end); if(a!=b)//无环 { parent[a]=b; sum+=Edge[i].weight; temp++; }
“被酒莫惊春睡重，赌书消得泼茶香，当时只道是寻常。”初见时仅仅是将它作为一个简单的递归转迭代的算法来看待，但之后再刷题时一而再再而三的遇上它，并且为它红了樱桃，却没能绿了芭蕉，经过查询方识卿之芳名------并查集：
是一种维护集合的数据结构，并查集三字分别取自："Union","FInd",""Set‘‘,初始化：
for(int i=1;i<=N;i++) { father[i]=i; }
FIND:
int findfather(int x) { while(father[x]!=x) { x=father[x]; } return x; }
Union：
void Union(int a,int b) { int m=findfather(a); int n=findfather(b); if(m!=n) { father[m]=n; }//反之，若相等则证明成环； } }
当然上述的算法时没有经过优化的，当元素成一条链式，一次向父节点进行查找会导致计算量过大，因而需要在find上做些手脚，即每一次查找完后，都让查找完的所有结点都指向统一的父节点，这样同一个集合中的查找就会缩短很多的时间：
Find:
int findfather(int x) { int a=x; while(x!=father[x]) { x=father[x]; } while(a!=father[a]) { int z=a; a=father[a]; father[z]=x;//将原先的根节点改为x; } }
这就是所谓的并查集算法；
举一道例题：
蓝桥杯和根植物：
#include<iostream> #include<string.h> using namespace std; int par[1000005]; int cnt; int n,m; int circle; int count; void init() { for(int i=1;i<=cnt;i++) { par[i]=i; } } int Find(int x) { int i=x; while(par[i]!=i) { i=par[i]; } int r=x; while(par[r]!=r) { int z=r; r=par[r]; par[z]=i; } return i; } void Union(int a,int b) { int m=Find(a); int n=Find(b); if(m!=n) { par[m]=n; } else { circle++; } } int main() { int u,v; cin>>m>>n; cnt=m*n; int k; cin>>k; init(); for(int i=1;i<=k;i++) { cin>>u>>v; Union(u,v); } for(int i=1;i<=cnt;i++) { if(par[i]==i) count++; } cout<<count<<endl; //cout<<circle<<endl;//多次一举，多输入个环的个数； }
原文：https://www.cnblogs.com/lszz/p/12003427.html