POJ - 1611 The Suspects解题报告

题目大意：n（30,000）个学生假如m（500）组，一个人可以加入多组，这堆学生被编号（0—n-1），编号为0的学生有病，一个组的人可以相互接触，问有多少人可以和0号学生接触（包括0号学生他自己） 

#include<iostream>#include<string.h>#define N 30000+500#define M 500+50using namespace std;int boss[N]={0};int n;int m;void init(){	for(int i=0;i<n;i++)	{		boss[i]=i;	}}void connect(int x,int y) {	if(x==0&&boss[y]==y)	{		boss[y]=0;		return;	}	if(y==0&&boss[x]==x)	{		boss[x]=0;		return;	}	if(boss[x]==x&&boss[y]==y)	{		boss[x]=y;		return;	}	boss[x]=boss[boss[x]];	boss[y]=boss[boss[y]];	connect(boss[x],boss[y]);}void ceshi1(){	for(int i=0;i<n;i++)	{		cout<<i<<":"<<boss[i]<<"   ";	} } int find(){	int s=0;	for(int i=0;i<n;i++)	{		int x=i;		while(1)		{			if(boss[x]==0)			{				//cout<<x;				s++;break;				}			/*cout<<i<<" "<<boss[i]<<"   ";			ceshi1();cout<<endl<<endl;*/			if(boss[x]==x)			{				break;			}			x=boss[x];		}	}	return s;}int main(){	while(cin>>n>>m)	{		if(m==0&&n==0)break;		init();		for(int i=0;i<m;i++)//输入m行数据 		{			int l;			cin>>l;			l--;			int x;			cin>>x;			while(l--)			{				int t;				scanf("%d",&t);				connect(x,t);			}		}		//ceshi1();		cout<<find()<<endl;	}}并查集，大概就是这样吧，然后注意别出现环，再写快一点。