文档章节

poj_1611The Suspects

N3verL4nd
 N3verL4nd
发布于 2017/03/25 10:45
字数 536
阅读 1
收藏 0
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
粉丝 1
博文 379
码字总数 481243
作品 0
朝阳
私信 提问
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
算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰
2016/04/02
155
1
一个搞ACM需要掌握的算法

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

long0404
2015/06/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

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

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
今天
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

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部