并查集

 1 #include <stdio.h>
 2 int f[1000] = {0},n,m,k,sum = 0;
 3 
 4 void init()//初始化 
 5 {
 6     int i;
 7     for(i = 1;i <= n;i++)
 8         f[i] = i;
 9 }
10 //找爹的递归函数，就是找犯罪集团的最高领导人 
11 int getf(int v)
12 {
13     if(f[v] == v)
14         return v;
15     else
16     {
17         f[v] = getf(f[v]);
18         return f[v];
19     }
20 }
21 void merge(int v,int u)
22 {
23     int t1,t2;
24     t1 = getf(v);
25     t2 = getf(u);
26     if(t1 != t2);//判断两个节点是否在同一个集合中 ，即是否为同一个祖先 
27     {
28         f[t2] = t1;
29         //靠左原则，左边的变成右边的boss 
30     }
31 }
32 
33 int main (void)
34 {
35     int i,x,y;
36     scanf("%d %d",&n,&m);
37     init();
38     for(i = 1;i<=m;i++)
39     {
40         //合并犯罪团伙 
41         scanf("%d %d",&x,&y);
42         merge(x,y);
43     }
44     for(i = 1;i <= n;i++)
45     {
46         if(f[i]==i)
47             sum++;
48     }printf("%d",sum);
49     return 0;
50  } 
测试数据：
10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4
结果：3
并查集也称不想交集数据结构
核心，擒贼先擒王，最终只有如f【i】 = i的，那么i就是犯罪团伙首领