#include <iostream>
#include <cstdio>
#include <cmath>
using namespace  std;
const int maxn = 30010;
int a[maxn],f[maxn];
int findx(int x){
    return f[x]<0?x:f[x]=findx(f[x]);
}
void bing(int a,int b){
    int t1 = findx(a);
    int t2 = findx(b);
    if(t1!=t2){
       if(t2==0){
        f[t2]+=f[t1];
        f[t1] = t2;
    }
    else{
        f[t1]+=f[t2];
        f[t2] = t1;
    }
    }
}
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0&&m==0)
            break;
        for(int i=0;i<n;++i) f[i] = -1;
        for(int i=1;i<=m;++i){
            int k;
            scanf("%d",&k);
            int t;
            for(int i=1;i<=k;++i){
                if(i==1){
                    scanf("%d",&t);
                    continue;
                }
                int s;
                scanf("%d",&s);
                bing(s,t);
            }
        }
        cout << abs(f[0])<<endl;
    }
    return 0;
}

• Re:经典并查集,16ms (1086) 703160327 2020-03-28 13:39:59
  • Re:经典并查集,16ms (2) 703160327 2020-03-28 13:40:26