POJ 1611.The Suspects-白红宇

POJ 1611.The Suspects

阅读量：4573 次

发布时间：2019-06-08

本文共 1812 字，大约阅读时间需要 6 分钟。

The Suspects

Time Limit:1000MS Memory Limit:20000KB 64bit IO Format:%I64d & %I64u

Submit
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
100 42 1 25 10 13 11 12 142 0 12 99 2200 21 55 1 2 3 4 51 00 0
Sample Output
411

将每个社团的第一个人看作队长，其队员所在的分支与队长所在的分支连接上。

遍历所有学生，与0在同一个分支的就是有可能感染的

AC代码：

1 /* 2 By:OhYee 3 Github:OhYee 4 HomePage:http://www.oyohyee.com 5 Email:oyohyee@oyohyee.com 6 Blog:http://www.cnblogs.com/ohyee/ 7  8 かしこいかわいい？ 9 エリーチカ！10 要写出来Хорошо的代码哦~11 */12 13 #include 
      
       14 #include 
       
        15 #include 
        
         16 #include 
         
          17 #include 
          
           18 #include 
           
            19 #include 
            
             20 #include 
             
              21 #include 
              
               22 #include 
               
                23 #include 
                24 using namespace std;25 26 //DEBUG MODE27 #define debug 028 29 //循环30 #define REP(n) for(int o=0;o
                 
                  < m;i++) {56 int num;57 scanf("%d",&num);58 int captain;//社团第一个设为组长59 scanf("%d",&captain);60 REP(num-1) {61 int temp;62 scanf("%d",&temp);63 uf[UF(temp)] = UF(captain);//将temp的根链接到captain的根上64 }65 }66 67 int cnt = 0;68 REP(n)69 if(UF(o)==UF(0))70 cnt++;71 72 /*REP(n)73 printf("%d %d\n",o,UF(o));*/74 75 printf("%d\n",cnt);76 77 78 return true;79 }80 81 int main() {82 while(Do());83 return 0;84 }