代码
(注释版)
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,f[10010],a,b,c;//数组f[i]记录i的根结点 4 int find(int x){ 5 if(f[x]==x) return x;//如果结点本身就是根结点,直接返回自己 6 else return f[x]=find(f[x]);//否则通过路径压缩递归返回根结点 7 } 8 void join(int x,int y){ 9 f[find(x)]=find(y);//通过find函数,合并两个结点x、y的根结点 10 return;//合并后别忘了直接返回 11 } 12 int main(){//好习惯,直接从主函数读起 13 cin>>n>>m; 14 for(int i=1;i<=n;i++) 15 f[i]=i;//初始化根结点数组,确保每个结点现在的根结点都是自己 16 for(int i=1;i<=m;i++){ 17 cin>>a>>b>>c; 18 if(a==1)//a为1时进行合并操作 19 join(b,c);//直接调用join()函数 20 else 21 if(find(b)==find(c))//当结点b、c的根结点相等时,则它们在一个集合里 22 cout<<"Y"<<endl; 23 else//否则它们不属于同一个集合 24 cout<<"N"<<endl; 25 } 26 return 0; 27 }
(无注释版)
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,f[10010],a,b,c; 4 int find(int x){ 5 if(f[x]==x) return x; 6 else return f[x]=find(f[x]); 7 } 8 void join(int x,int y){ 9 f[find(x)]=find(y); 10 return; 11 } 12 int main(){ 13 cin>>n>>m; 14 for(int i=1;i<=n;i++) 15 f[i]=i; 16 for(int i=1;i<=m;i++){ 17 cin>>a>>b>>c; 18 if(a==1) 19 join(b,c); 20 else 21 if(find(b)==find(c)) 22 cout<<"Y"<<endl; 23 else 24 cout<<"N"<<endl; 25 } 26 return 0; 27 }
总结
并查集分3步:
1. 把每个结点所在的集合初始化为它自己
2. 将两个不同集合的结点合并(join函数)
3. 查找结点所在集合的根结点(find函数)
经典例题:
原文链接: https://www.cnblogs.com/integricode26/p/union-find-disjoint-sets-template.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/368768
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!