首页 > 代码库 > HDU - 1213 How Many Tables

HDU - 1213 How Many Tables

2024-07-14 17:27:15   224人阅读

题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=1213

典型的并查集，属于水题吧，但学会了路径压缩。

 1 /*非递归，非路径压缩*/ 2 #include<stdio.h> 3 const int maxn=1000+5; 4 int fa[maxn]; 5 void init(int n) 6 { 7     for(int i=1;i<=n;i++) 8         fa[i]=0; 9 }10 int find_father(int x)11 {12     while(fa[x]!=0){13         x=fa[x];14     }15     return x;16 }17 void union_father(int x,int y)18 {19     int find_a=find_father(x),find_b=find_father(y);20     if(find_a!=find_b)21         fa[find_b]=find_a;22 }23 int main()24 {25     int t;26     scanf("%d",&t);27     while(t--){28         int n,m,a,b;29         scanf("%d%d",&n,&m);30         init(n);31         for(int i=1;i<=m;i++){32             scanf("%d%d",&a,&b);33             union_father(a,b);34         }35         int ans=0;36         for(int i=1;i<=n;i++)37             if(fa[i]==0)38             ans++;39         printf("%d\n",ans);40     }41     return 0;42 }
 1 /*递归，路径压缩*/ 2 #include<stdio.h> 3 const int maxn=1000+5; 4 int fa[maxn]; 5 void init(int n) 6 { 7     for(int i=1;i<=n;i++) 8         fa[i]=0; 9 }10 int find_father(int x)11 {12     if(fa[x]==0)13         return x;14     fa[x]=find_father(fa[x]);15     return fa[x];16 }17 void union_father(int x,int y)18 {19     int find_a=find_father(x),find_b=find_father(y);20     if(find_a!=find_b)21         fa[find_b]=find_a;22 }23 int main()24 {25     int t;26     scanf("%d",&t);27     while(t--){28         int n,m,a,b;29         scanf("%d%d",&n,&m);30         init(n);31         for(int i=1;i<=m;i++){32             scanf("%d%d",&a,&b);33             union_father(a,b);34         }35         int ans=0;36         for(int i=1;i<=n;i++)37             if(fa[i]==0)38             ans++;39         printf("%d\n",ans);40     }41     return 0;42 }

 


联系
我们