POJ 1611 – The Suspects (并查集)

原题地址:《The Suspecst》

题目大意:某学校有N个学生,M个社团,每个学生可以属于多个社团。SARS流行,但是社团活动频繁,一旦一个社团有一个人是SARS疑似,所有人都是SARS疑似。现在假定第0号学生是SARS疑似,求所有疑似病例。

这个就是典型的并查集问题……我挑了这个最水的问题实践了一下。和刚才哪篇并查集无异。数据弱所以连rank union都不用就能过。

思路是:每个社团读取后直接把他们union起来。最后将学生0的parent和其他N-1个学生比较(来判断他们是否属于一个集合),如果一样的,sum++。最后输出sum。

代码是有优化余地的:实际上,每次union的时候就能知道每个set有多少新元素。这样就不用最后再遍历依次n个学生的find_set了!

#include <stdio.h>
#define MAX 30001

int parent[MAX];
int num[MAX];

int find_set(int x)
{
	if(x!=parent[x])
	{
		int tmp = find_set(parent[x]);
		parent[x] = tmp;
	}
	return parent[x];
}

int union_set(int x, int y)
{
	int x_parent = find_set(x);	
	int y_parent = find_set(y);
	parent[x_parent] = parent[y_parent];
}

int main()
{
	int n,m;
	int i, j;
	int k;
	int first;
	int member;
	int sus;
	int sum;
	while(scanf("%d %d", &n, &m)!=EOF)
	{
		if(n==0 && m==0)
		{
			break;
		}
		// Init set
		for(i=0;i<n;i++)
		{
			parent[i] = i;
		}
		// Read each group and union member in each group
		for(i=0;i<m;i++)
		{
			scanf("%d", &k);
			scanf("%d", &first);
			for(j=1;j<k;j++)
			{
				scanf("%d", &member);	
				union_set(first, member);
			}
		}
		// Get suspect [0]'s parent
		int sus = find_set(0);
		sum = 0;
		for(i=0;i<n;i++)
		{
			if(find_set(i)==sus)
			{
				sum++;
			}
		}
		printf("%d\n", sum);
	}
}

Leave a Reply

Your email address will not be published.