POJ 1661

• 带权并查集模板
• 并查集+统计一个点集的大小

  #include <iostream>
  using namespace std;
  const int maxn = 3e4+10;
  int n,m;
  int prv[maxn];
  int tot[maxn]; // tot记录以点i作为顶点的个数 
  int find(int x) {
  	if ( prv[x] == x ) return x;
  	return prv[x] = find(prv[x]);
  }
  void merge(int a,int b) {
  	int p1 = find(a);
  	int p2 = find(b);
  	if ( p1==p2 ) return ;
  	prv[p2] = p1;
  	tot[p1] += tot[p2]; 
  }
  void init(int n) {
  	for (int i=0; i<n; i++) 
  		prv[i] = i,tot[i] = 1; 
  }
  int main() {
  //	freopen("a.txt","r",stdin); 
  	while ( scanf("%d%d",&n,&m) ) {
  		if ( n==0 && m==0 ) break;
  		init(n);
  		for (int i=0 ; i<m; i++) {
  			int cur,k;
  			scanf("%d%d",&k,&cur);
  			for (int j=1; j<k; j++) {
  				int v;
  				scanf("%d",&v);
  				merge(cur,v);
  			}
  		} 
  		printf("%d\n", tot[find(0)] );
  	}
  	return 0;
  }