The Suspects POJ - 1611（并查集）

使用并查集的同時記錄每一個集合的元素個數size

#include<iostream>
using namespace std;
typedef long long ll;
const int N=30005;
int size[N],p[N];

int find(int x){
    if(p[x]!=x) return p[x]=find(p[x]);
    return p[x];
}

int main(){
	int n,m;
	while(scanf("%d%d",&n,&m)&&n){  
            for(int i=0;i<=30000;++i) {//每組case 初始化
                p[i]=i;
                size[i]=1;
            }
            for(int j=0;j<m;++j){//m個社團
                int k,A;
                scanf("%d",&k);
                scanf("%d",&A);
                int fA=find(A);
                for(int i=1;i<k;++i){
                    int a;
                    scanf("%d",&a);
                    int fa=find(a);
                    if(fa!=fA) size[fA]+=size[fa];//統計連通塊的大小
                    p[fa]=fA;
                }
            }
            printf("%d\n",size[find(0)]);        
	}
}