## poj_1611The Suspects 原

The Suspects
 Time Limit: 1000MS Memory Limit: 20000K Total Submissions: 17471 Accepted: 8426

Description

Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.
In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).
Once a member in a group is a suspect, all members in the group are suspects.
However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects.

Input

The input file contains several cases. Each test case begins with two integers n and m in a line, where n is the number of students, and m is the number of groups. You may assume that 0 < n <= 30000 and 0 <= m <= 500. Every student is numbered by a unique integer between 0 and n−1, and initially student 0 is recognized as a suspect in all the cases. This line is followed by m member lists of the groups, one line per group. Each line begins with an integer k by itself representing the number of members in the group. Following the number of members, there are k integers representing the students in this group. All the integers in a line are separated by at least one space.
A case with n = 0 and m = 0 indicates the end of the input, and need not be processed.

Output

For each case, output the number of suspects in one line.

Sample Input

``````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

``````4
1
1``````

``````#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 30005
int father[MAX],ranks[MAX];

void Make_Set(int n)
{
for(int i = 0;i < n; i++)
{
father[i] = i;
ranks[i] = 0;
}
}

int Find_Set(int x)
{
if(x != father[x])
{
father[x] = Find_Set(father[x]);//路径压缩
}
return father[x];
}

void Merge_Set(int x,int y)
{
x = Find_Set(x);
y = Find_Set(y);
if(x == y) return;
if(ranks[x] > ranks[y])
{
father[y] = x;
}
else if(ranks[x] < ranks[y])
{
father[x] = y;
}
else
{
ranks[y]++;
father[x] = y;
}
}

int main()
{
freopen("in.txt", "r", stdin);
vector<int>temp;
int n, m, t, stu, y, sum;
while(cin >> n >> m)
{
sum = 0;
if(n == 0 && m == 0) break;
Make_Set(n);
while(m--)
{
cin >> t >> stu;
temp.push_back(stu);
for(int i = 1; i < t; i++)
{
cin >> y;
temp.push_back(y);
Merge_Set(stu,y);
stu = y;
}
}
sort(temp.begin(), temp.end());
temp.erase(unique(temp.begin(), temp.end()), temp.end());
int x = Find_Set(0);
for(int i = 0; i < temp.size(); i++)
{
if(x == Find_Set(temp[i]))
{
sum++;
}
if(sum == 0)
{
sum++;
}
}
cout<< sum <<endl;
}
return 0;
}``````

© 著作权归作者所有 ### N3verL4nd

POJ The Suspects

Description Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission t......

zoom1109
06/14
0
0
POJ611 The Suspects并查集+优先队列

POJ1611 题目大意: 非典来袭 n 个人 m 个团队， n个人的编号为0 --- n-1 其中已知 0 被怀疑携带非典病毒，如果一个队伍中有一个人是 被怀疑携带有此病毒，那么这一个团队中的所有人都被i怀疑...

zhagoodwell
2018/01/15
0
0
POJ ~ 1611 ~ The Suspects （并查集）

ZscDst
2018/01/17
0
0

2016/04/02
155
1

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段：练经典常用...

long0404
2015/06/24
0
0

《Designing.Data-Intensive.Applications》笔记 四

5
0
docker 使用mysql

1， 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互： exit 3. mysql 启动在容器里面，并且 可以本地连接mysql docker run --name mysql1 --env MY...

6
0
python数据结构

1、字符串及其方法（案例来自Python-100-Days） def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue

4
0
OSChina 周日乱弹 —— 我，小小编辑，食人族酋长

Osc乱弹歌单（2019）请戳（这里） 【今日歌曲】 @宇辰OSC ：分享娃娃的单曲《飘洋过海来看你》: #今日歌曲推荐# 《飘洋过海来看你》- 娃娃 手机党少年们想听歌，请使劲儿戳（这里） @宇辰OSC...

1K
11
MongoDB系列-- SpringBoot 中对 MongoDB 的 基本操作

SpringBoot 中对 MongoDB 的 基本操作 Database 库的创建 首先 在MongoDB 操作客户端 Robo 3T 中 创建数据库: 增加用户User: 创建 Collections 集合（类似mysql 中的 表）： 后面我们大部分都...

TcWong

40
0 