杭电1232畅通工程-并查集

本文主要是介绍杭电1232畅通工程-并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

并查集：

主要函数：

int getfather(int x)
{return father[x]!=x?father[x]=getfather(father[x]):x;
}void uni(int x,int y)
{int fx = getfather(x),fy = getfather(y);if(fx==fy)return ;father[fx]=fy;
}

1232代码：

#include<stdio.h>
#include<iostream>
using namespace std;
int father[1005];
int getfather(int x)
{return father[x]!=x?father[x]=getfather(father[x]):x;
}
void uni(int x,int y)
{int fx = getfather(x),fy = getfather(y);if(fx==fy)return ;father[fx]=fy;
}
int main()
{int n,m;while(cin>>n>>m && n){ int sum=0,i,j;for(i=1;i<=n;i++)father[i]=i;int a,b;for(i=1;i<=m;i++){cin>>a>>b;uni(a,b);}for(i=1;i<=n;i++)if(getfather(i)==i)sum++;
//        for(i=1;i<=n;i++)cout<<getfather(i)<<" ";cout<<endl;cout<<sum-1<<endl;}return 0;
}

这篇关于杭电1232畅通工程-并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---