首页 > 其他 > 详细

ZOJ 1789 The Suspects

时间:2014-04-21 00:22:15      阅读:531      评论:0      收藏:0      [点我收藏+]

与2833差不多

基本上只是merge函数那里的优先做父亲的条件改一下便可提高效率...

bubuko.com,布布扣
 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\n",-parent[0]);
51     }
52 
53     return 0;
54 }
View Code

 

ZOJ 1789 The Suspects,布布扣,bubuko.com

ZOJ 1789 The Suspects

原文:http://www.cnblogs.com/imLPT/p/3675952.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!