poj 1611（并查集）

这次写并查集比上一题有太多的优化了，oh yeah! 注意其中的压缩优化……

#include <iostream>
#include<cstdio>
#include <queue>
#include<string.h>
using namespace std;
int pre[30005];
int num[30005];
void makeSet(int n)
{
	for(int i=0;i<n;i++)
	{
		num[i]=1;
		pre[i]=i;
	}
}
int findSet(int m)
{
	if(pre[m]!=m)
		pre[m]=findSet(pre[m]);//特别注意此处的压缩 ~\(≧▽≦)/~ 与m=findSet(pre[m]);还是有区别的
	return pre[m];
}
void unionSet(int m,int n)
{
	int mm=findSet(m);
	int nn=findSet(n);
	if(mm==nn)
		return;
	if(num[mm]>num[nn])//压缩层次
	{
		pre[nn]=mm;
		num[mm]+=num[nn];
	}
	else
	{
		pre[mm]=nn;
		num[nn]+=num[mm];
	}
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)&&(n+m))
	{
		makeSet(n);
		while(m--)
		{
			int len,fr,sc;
			cin>>len>>fr;
			for(int i=1;i<len;i++)
			{
				cin>>sc;
				unionSet(fr,sc);
			}
		}
		cout<<num[findSet(0)]<<endl;
	}
}