hdu 1213

 1 #include<stdio.h>
 2 int f[10005],n,m;
 3 
 4 //初始化 
 5 void init()
 6 {
 7     for(int i=1;i<=n;i++)
 8         f[i]=i;
 9 } 
10 //递归函数，不停的去找爹，直到找到祖宗为止 
11 int getf(int v)
12 {
13     if(v == f[v])
14         return v;
15     //路径压缩，函数返回时改变了爹的值，有利于后面找祖宗 
16     else
17     {
18         f[v]=getf(f[v]);
19         return f[v];
20     }
21 }
22 
23 //合并两个子集的函数 
24 void merge(int u,int v)
25 {
26     int t1=getf(u);
27     int t2=getf(v);
28     //判断两个结点是不是在同一个集合中 即是不是共祖宗 
29     if(t1 != t2)
30     {
31         f[t2]=t1;
32         //靠左原则，将右边集合变成左边的子集合
33         //经过路径压缩后将f[u]的根的值也赋值为v的祖先f[t1] 
34     }
35 }
36 
37 int main()
38 {
39     int x,y,sum,num;
40     while(scanf("%d",&num)!=EOF)
41     {
42         while(num--)
43         {
44             scanf("%d %d",&n,&m);
45             {
46                 sum=0;
47                 //初始化 
48                 init();
49                 
50                 for(int i=1;i<=m;i++)
51                 {
52                     //开始合并 
53                     scanf("%d %d",&x,&y);
54                     merge(x,y);
55                 }
56                 
57                 //扫描连通分支数 
58                 for(int i=1;i<=n;i++)
59                 {
60                     if(f[i] == i)
61                     sum++;
62                 }
63                 printf("%d\n",sum);
64             }
65         }
66     }
67     return 0;
68 }