赤裸裸的并查集,我还是习惯那位大牛写的方法,首先写出两个数组:father[i]=i和son[i]=1,然后依次查找元素并且使用路径压缩+权值压缩
#include<iostream> #include<cstdio> using namespace std; #define MAX 1000 int son[MAX]; int father[MAX]; int find(int x) { return x == father[x] ? x : find(father[x]); } void Union(int x,int y) { int root1=find(x); int root2=find(y); if(son[root1]>=son[root2]) { father[root2]=root1; son[root1]+=son[root2]; } else { father[root1]=root2; son[root2]=root1; } } int main() { // freopen("1232.txt","r",stdin); int i,n,k,a,b;//n城市数目,k道路条数,a,b道路条数起始点 while(1) { int count=-1; scanf("%d",&n); if(n==0) break; for(i=1;i<=n;i++)//初始化father[],son[] { father[i]=i; son[i]=1; } scanf("%d",&k); for(i=0;i<k;i++) { scanf("%d%d",&a,&b); Union(a,b); } for(i=1;i<=n;i++) { if(father[i]==i) { count++; } } printf("%d\n",count); } return 0; }
在kruskal中正是运用的并查集的方法实现两个集合的合并