問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1611思路:
話說(shuō)是最基礎(chǔ)的并查集，每個(gè)分支的根節(jié)點(diǎn)賦予該分支節(jié)點(diǎn)個(gè)數(shù)的相反數(shù)，妙...
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 30001
5 int parent[MAX_LEN];
6
7 void
8 init(int size)
9 {
10 int i;
11 for(i=0; i<size; i++)
12 parent[i] = -1;
13 }
14
15 int
16 find(int item)
17 {
18 int tmp, root = item;
19 while(parent[root] >= 0)
20 root = parent[root];
21 while(item != root) {
22 tmp = parent[item];
23 parent[item] = root;
24 item = tmp;
25 }
26 return root;
27 }
28
29 void
30 uunion(int item1, int item2)
31 {
32 int root1 = find(item1);
33 int root2 = find(item2);
34 if(root1 != root2) {
35 if(parent[root1] < parent[root2]) { /* tree with 'root1' has more nodes */
36 parent[root1] += parent[root2];
37 parent[root2] = root1;
38 } else {
39 parent[root2] += parent[root1];
40 parent[root1] = root2;
41 }
42 }
43 }
44
45 int
46 main(int argc, char **argv)
47 {
48 int n, m, gp, i, j, r, stu;
49 while(scanf("%d %d", &n, &m)!=EOF) {
50 if(n==0 && m==0)
51 break;
52 init(n);
53 for(i=0; i<m; i++) {
54 scanf("%d", &gp);
55 for(j=0; j<gp; j++) {
56 scanf("%d", &stu);
57 if(j==0)
58 r = stu;
59 else
60 uunion(r, stu);
61 }
62 }
63 printf("%d\n", -parent[find(0)]);
64 }
65 }