http://poj.org/problem?id=1611
并查集的基本应用题
View Code
1 #include <stdio.h>
2 #include <stdlib.h>
3 int father[30005],num[30005];
4
5 void make_set(int x)
6 {
7 father[x] = x;
8 num[x] = 1;
9 }
10
11 //查找x元素所在的集合,回溯时压缩路径
12 int find_set(int x)
13 {
14 if(x != father[x])
15 {
16 father[x] = find_set(father[x]);//这个回溯时的压缩路径是精华
17 }
18 return father[x];
19 }
20
21 void union_set(int a,int b)
22 {
23 a = find_set(a);
24 b = find_set(b);
25 if(a == b) return ;
26 if(num[a] <= num[b])
27 {
28 father[a] = b;
29 num[b] += num[a];
30 }
31 else
32 {
33 father[b] = a;
34 num[a] += num[b];
35 }
36 }
37 int main()
38 {
39 int n,m,a,b,t,i,j;
40 while(scanf("%d %d",&n,&m) == 2)
41 {
42 if(n + m == 0) break;
43 for(i = 0;i < n;i ++)
44 {
45 make_set(i);
46 }
47 for(i = 0;i < m;i ++)
48 {
49 scanf("%d",&t);
50 scanf("%d",&a);
51 for(j = 1;j < t;j ++)
52 {
53 scanf("%d",&b);
54 union_set(a,b);
55 }
56 }
57 printf("%d\n",num[find_set(0)]);
58 }
59 return 0;
60 }