B - The Suspects POJ - 1611

72 阅读 0 评论 48 点赞

我是靠谱客的博主开放小蘑菇，最近开发中收集的这篇文章主要介绍B - The Suspects POJ - 1611，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意：

非典期间啊，在一个叫不传播疾病（？？？）的大学里，学生会参与几个小组。但是有的人可能患有SARS，他也可能会参加小组，这样的话，和他同一个小组的所有人也会被认为有患病的可能。判断判断有多少人可能是嫌疑人？多组测试。第一行输入n和m，n表示学生人数，m表示小组个数。接下来m行，每行第一个x代表这个小组的人数，剩下的是成员的编号（0~n-1）。我们默认，0号是学生里的嫌疑人。当输入m==0&&n==0的时候，结束。（n<=30000，m<=500）

参考思路：

把小组里的人呐都连起来，都和出现的第一个人连就好啦。然后把0的根节点的尺寸输出来就好了。（emmmm ？这么简单？

 1 #include <iostream>
 2 #include <vector>
 3 #include <map>
 4 #include <string>
 5 #include <queue>
 6 #include <stack>
 7 #include <set>
 8 
 9 #include <cstdio>
10 #include <cstring>
11 #include <cmath>
12 #include <cstdlib>
13 using namespace std;
14 
15 const int INF=0x3f3f3f3f;
16 const int SIZE=30010;
17 
18 int id[SIZE],sz[SIZE];
19 
20 int find(int x)
21 {
22     while(x!=id[x])
23     {
24         id[x]=id[id[x]];
25         x=id[x];
26     }
27     return x;
28 }
29 void un(int p,int q)
30 {
31     int pr=find(p);
32     int qr=find(q);
33     if(pr==qr) return;
34     if(sz[pr]<sz[qr])
35     {
36         id[pr]=qr;sz[qr]+=sz[pr];
37     }
38     else
39     {
40         id[qr]=pr;sz[pr]+=sz[qr];
41     }
42 }
43 
44 
45 int main()
46 {
47     int n,m;
48     while(scanf("%d%d",&n,&m))
49     {
50         if(m==0&&n==0) break;
51         int i,j,k,num,first,next;
52         for(i=0;i<n;i++)
53         {
54             id[i]=i;
55             sz[i]=1;
56         }
57         for(i=0;i<m;i++)
58         {
59             scanf("%d",&num);
60             scanf("%d",&first);
61             for(j=1;j<num;j++)    ///key
62             {
63                 scanf("%d",&next);
64                 un(first,next);
65             }
66         }
67         printf("%dn",sz[find(0)]);
68     }
69     return 0;
70 }