问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2524思路:
简单并查集，求连通分支的个数，一次AC
代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_NUM 50001
5 int father[MAX_NUM];
6 int rank[MAX_NUM];
7 int total;
8
9 void
10 init(int n)
11 {
12 int i;
13 for(i=1; i<=n; i++)
14 father[i] = i;
15 memset(rank, 0, sizeof(rank));
16 total = n;
17 }
18
19 int
20 find(int item)
21 {
22 if(father[item] != item)
23 father[item] = find(father[item]);
24 return father[item];
25 }
26
27 void
28 uunion(int item1, int item2)
29 {
30 int a = find(item1);
31 int b = find(item2);
32 if(a == b)
33 return;
34 --total;
35 if(rank[a] > rank[b])
36 father[b] = a;
37 else {
38 father[a] = b;
39 if(rank[a] == rank[b])
40 ++rank[b];
41 }
42 }
43
44 int
45 main(int argc, char **argv)
46 {
47 int n, m, i, j, k, cnt=0;
48 while(scanf("%d %d", &n, &m)!=EOF) {
49 if(n==0 && m==0)
50 break;
51 init(n);
52 for(k=0; k<m; k++) {
53 scanf("%d %d", &i, &j);
54 uunion(i, j);
55 }
56 printf("Case %d: %d\n", ++cnt, total);
57 }
58 }