poj 1611

107 阅读 0 评论 71 点赞

我是靠谱客的博主光亮超短裙，这篇文章主要介绍poj 1611，现在分享给大家，希望可以做个参考。

Description

严重急性呼吸系统综合症( SARS), 一种原因不明的非典型性肺炎,从2003年3月中旬开始被认为是全球威胁。为了减少传播给别人的机会, 最好的策略是隔离可能的患者。

在Not-Spreading-Your-Sickness大学( NSYSU), 有许多学生团体。同一组的学生经常彼此相通,一个学生可以同时加入几个小组。为了防止非典的传播,NSYSU收集了所有学生团体的成员名单。他们的标准操作程序(SOP)如下：

一旦一组中有一个可能的患者, 组内的所有成员就都是可能的患者。

然而,他们发现当一个学生被确认为可能的患者后不容易识别所有可能的患者。你的工作是编写一个程序, 发现所有可能的患者。

Input

输入文件包含多组数据。

对于每组测试数据：

第一行为两个整数n和m, 其中n是学生的数量, m是团体的数量。0 < n <= 30000，0 <= m <= 500。

每个学生编号是一个0到n-1之间的整数，一开始只有0号学生被视为可能的患者。

紧随其后的是团体的成员列表，每组一行。

每一行有一个整数k，代表成员数量。之后,有k个整数代表这个群体的学生。一行中的所有整数由至少一个空格隔开。

n = m = 0表示输入结束，不需要处理。

Output

对于每组测试数据, 输出一行可能的患者。

Sample Input

复制代码

1
2
3
4
5
6
7
8
9
10
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0

Sample Output

复制代码

并查集的简单应用，在上一篇博客中有详细的介绍

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>

using namespace std;
int pre[30100];
int find(int x)
{
 int r=x;
 while(pre[r]!=r)
 {
  r=pre[r];
 }
 int i=x,j;
 while(i!=r)
 {
  j=pre[i];
  pre[i]=r;
  i=j;
 }
 return r;
}
void join(int x,int y)
{
  int fx=find(x),fy=find(y);
  if(fx!=fy)
   pre[fx]=fy;
}
int main()
{
    int n,m,t,a,b,tmp,ans;
    while(cin>>n>>m)
    {
     if(n==0&&m==0)
      break;
      for(int i=0;i<=n-1;i++)
      {
      pre[i]=i;
      }
     for(int i=0;i<=m-1;i++)
     {
      cin>>t>>a;
      for(int j=1;j<=t-1;j++)
      {
       cin>>b;
       join(a,b);
      }
     }
     tmp=find(0);
     ans=0;
     for(int i=0;i<=n-1;i++)
     {
      if(find(i)==tmp)
       ans++;
     }
    cout << ans << endl;
    }
    return 0;
}