POJ---1611（并查集，求规模，按规模归并）

题意：

N个学生，m个团体，0号学生带传染病，每个集合内有一个带传染病的，则会感染该集合内所有的学生。

题解：

并查集基础题，归并函数写的时候要按照按规模归并。根节点root的parents【root】=-k记录集合的规模k。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
#include<functional>
#include<utility>
#include<set>
#include<map>
#include<cmath>
#include<stack>using namespace std;const int maxn=30000+5;int pa[maxn];int findset(int x)
{return pa[x]<0? x: pa[x]=findset(pa[x]);
}void unionset(int x, int y)//按规模归并,树根的父亲存放负的规模。
{int rx=findset(x),ry=findset(y);if(rx==ry)return;if(pa[rx]<pa[ry])//rx集合大{  pa[rx]+=pa[ry];pa[ry]=rx;}else{pa[ry]+=pa[rx];pa[rx]=ry;}
}int main()
{int n,m;while(cin>>n>>m,n||m){   memset(pa,-1,sizeof(pa));while(m--){int k;cin>>k;int x,y;cin>>x;k--;while(k--){cin>>y;unionset(x,y);}}cout<<-pa[findset(0)]<<endl;}
}