【 POJ - 1611】The Suspects（简单并查集）

The Suspects 

 POJ - 1611

严重急性呼吸系统综合症（SARS）是一种不明病因的非典型肺炎，于2003年3月中旬被确认为全球威胁。为了尽量减少向他人的传播，最好的策略是将嫌疑人与其他人分开。
在不扩散你的疾病大学（NSYSU），有许多学生团体。同一组的学生经常相互交流，学生可以加入几个小组。为防止SARS的可能传播，NSYSU收集了所有学生团体的成员名单，并在其标准操作程序（SOP）中做出了以下规定。
一旦组成员是嫌疑人，则组中的所有成员都是嫌疑人。
然而，他们发现，当一个学生被确认为嫌疑人时，要识别所有嫌疑人并不容易。你的工作是写一个程序，找到所有的嫌疑人。

输入

输入文件包含多个案例。每个测试案例以两个整数 n 和 m 开始，其中 n 是学生人数，m 是组数。您可以假设 0 < n < = 30000 和 0 <= m <= 500。每个学生都按 0 到 n+1 之间的唯一整数编号，最初学生 0 在所有案例中都被确认为嫌疑人。此行后面是组的 m 成员列表，每个组一行。每行以代表组成员数的整数 k 开头。根据成员人数，有代表该组学生的 k 整数。线路中的所有整数都至少由一个空间隔开。
n = 0 和 m = 0 的案例表示输入的结束，无需处理。

输出

对于每个案件，将嫌疑人数量输出到一行中。

示例输入

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

样品输出

4

1

1

题意描述：多实例，给学生的人数n（学生按0~n-1编号）以及学生组数m，然后是每组学生成员以及学生编号信息，同一组的学生可以加入好几个小组。其中学生编号为0的是嫌疑人，一旦与学生0为一组或它的组内成员还加入了其他组，他们都是嫌疑人，求嫌疑人数量。

解题思路：因为学生根据学生人数从0开始编号，也就是只要学生人数大于1，就至少有1个嫌疑人，可以利用并查集来划分学生的不相交集合，再记录学生0所在的集合的学生人数输出。

AC

#include<stdio.h>
int n,m;
int s[30100]={0};

int getf(int v)
{
	if(s[v]==v)
		return v;
	else
	{
		s[v]=getf(s[v]);
		return s[v]; 
	}
	
 } 
//合并两个子集
void merge(int v,int u)
{
	int t1,t2;
	t1=getf(v);
	t2=getf(u);
	if(t1!=t2)
	{
		s[t2]=t1;
	}
	return ;
 } 

int main(void)
{
	int d,a,b,sum,ans;
	
	while(~scanf("%d %d",&n,&m))//学生，组数 
	{
		if(n+m==0)
			break;
		for(int i=0;i<n;i++)
			s[i]=i;
		for(int i=0;i<m;i++)
		{
			scanf("%d",&d);//每组人数 
			scanf("%d",&a);//前一个 
			for(int k=1;k<d;k++)
			{
				scanf("%d",&b);//后面的 
				//合并 
				merge(a,b);
			}
				 
		} 
		sum=0;
		for(int i=0;i<n;i++)
		{
			if(getf(i)==getf(0))
			sum++;
		}	
		printf("%dn",sum);
	}
	return 0;
 }

最后

以上就是拉长大地为你收集整理的【 POJ - 1611】The Suspects（简单并查集）的全部内容，希望文章能够帮你解决【 POJ - 1611】The Suspects（简单并查集）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。