ZOJ 1789 The Suspects

与2833差不多
基本上只是merge函数那里的优先做父亲的条件改一下便可提高效率...
 1 //The Suspects
 2 #include<cstdio>
 3 #include<memory.h>
 4 int parent[30001];
 5 int find(int i)
 6 {
 7     while(parent[i] >= 0)
 8         i = parent[i];
 9     return i;
10 }
11 void merge(int a,int b)
12 {
13     int c = find(a);
14     int d = find(b);
15     int temp = parent[c] + parent[d];
16     if(c != d)
17     {
18         if(d < c)//d的根小于c,d做父亲。。。因为0是感染者，这样建立查找时有效率
19         {
20             parent[c] = d;
21             parent[d] = temp;
22         }
23         else
24         {
25             parent[d] = c;
26             parent[c] = temp;
27         }
28     }
29 }
30 int main()
31 {
32     //freopen("input.txt","r",stdin);
33     int n,m;
34     int k,a,b;
35     while(scanf("%d%d",&n,&m) && n)//这里不能scanf("%d%d",&n,&m) && n && m) 因为m为0时同样可以
36     {
37         memset(parent,-1,sizeof(parent));
38         while(m--)
39         {
40             scanf("%d",&k);
41             scanf("%d",&a);
42             k--;
43             while(k--)
44             {
45                 scanf("%d",&b);
46                 merge(a,b);
47             }
48 
49         }
50         printf("%d
",-parent[0]);
51     }
52 
53     return 0;
54 }