首页 > 代码库 > hdu 1213 How Many Tables

hdu 1213 How Many Tables

http://acm.hdu.edu.cn/showproblem.php?pid=1213

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 2000
 5 using namespace std;
 6 
 7 int f[maxn],n,m;
 8 
 9 void inti()
10 {
11     for(int i=1; i<=n; i++)
12     {
13         f[i]=i;
14     }
15 }
16 
17 int find1(int x)
18 {
19     if(x==f[x]) return x;
20     return f[x]=find1(f[x]);
21 }
22 
23 void union2(int a,int b)
24 {
25     int fa=find1(a);
26     int fb=find1(b);
27     if(fa!=fb)
28     {
29         f[fa]=fb;
30     }
31 }
32 
33 int main()
34 {
35     int t;
36     scanf("%d",&t);
37     while(t--)
38     {
39         scanf("%d%d",&n,&m);
40         inti();
41         for(int i=1; i<=m; i++)
42         {
43             int a1,b1;
44             scanf("%d%d",&a1,&b1);
45             union2(a1,b1);
46         }
47         int ans=0;
48         for(int i=1; i<=n; i++)
49         {
50             if(f[i]==i) ans++;
51         }
52         printf("%d\n",ans);
53     }
54     return 0;
55 }
View Code