B - The Suspects（并查集算法）

65 阅读 0 评论 43 点赞

我是靠谱客的博主自然黑裤，最近开发中收集的这篇文章主要介绍B - The Suspects（并查集算法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

B - The Suspects（并查集算法）

严重急性呼吸系统综合症(SARS)是一种病因不明的非典型肺炎，在2003年3月中旬被确认为全球威胁。为了尽量减少传染给他人，最好的策略是把嫌疑犯和其他人分开。在非传播疾病大学（NSYSU）中，有许多学生团体。同组的学生经常互相交流，一个人可能会加入多个组。为防止SARS可能传播，NSYSU收集所有学生群体的成员名单，并在其标准操作过程中制定以下规则。（SOP）。集团中的一个成员是一个嫌疑人，集团中的所有成员都是嫌疑人。然而，他们发现，当学生被认定为嫌疑人时，不容易识别所有的嫌疑人。你的工作是写一个程序找出所有嫌疑人。
Input
输入文件包含几种情况。每个测试用例从一行中的两个整数n和m开始，其中n是学生的数目，m是组的数目。你可以假设0<n<=30000 和0<=m<=500。每个学生都由0到n−1之间的唯一整数编号，在所有情况下，最初都将学生0识别为嫌疑犯。行后面跟着m个成员列表。组，每组一行。每一行的开头都是一个整数k，表示组中的成员数。在成员数之后，有代表学生的k个整数。在这组中。一行中的所有整数至少用一个空格分隔。n=0和m=0的情况表示输入的结束，不需要处理。
Output
在每一个案件中，输出一行嫌疑犯的数量。
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

题意描述：现在有一种传染性很强的病，为了防止疾病的传播需要找到感染者或有感染嫌疑的人，一群人被分为多组，一组中如果有一个嫌疑人即认为一组人都为嫌疑人，现在确定的只有0号为嫌疑人，给出人数n和，m条线索，每条线索的第一个数代表改组的人数，一个人可以加入不同的分组，找出嫌疑人的总数量；
解题思路：先用并查集的方法将所有的人都连接到一块，每个组的人都有相同的boss；再找到到所有与0的boss相同的即是嫌疑人，不能用上一级直接比较，因为它能可能不是直属于boss的；因此无法比较。
错误分析：不能用上一级直接比较，因为它能可能不是直属于boss的；因此无法比较。

#include<stdio.h>
int a[51005],m,n;
void init(int n)
{
	int i;
	a[0]=0;
	for(i=1;i<=n;i++)
	   a[i]=i;
	return;
}
int getf(int v)
{
	if(a[v]==v)
	return v;
	else
	{
		a[v]=getf(a[v]);
		return a[v];
	}
}
void merge(int x,int y)
{
	int t1,t2;
	t1=getf(x);
	t2=getf(y);
	if(t1!=t2)
	  a[t2]=t1;
	return;
}
int main()
{
	int i,j,k,x,y,z,sum,t=0;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(m==0 && n==0)
		break;
		sum=0;
		init(n);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			x--;
			while(x--)
			{
				scanf("%d",&z);
				merge(y,z);
				y=z;
			}
		}
		x=getf(0);
		for(i=0;i<=n;i++)
		{
		//	printf("%d* ",getf(i));
			if(getf(i)==x)
		    sum++;
		}
		printf("%dn",sum);
	}
	return 0;
}