POJ1611 The Suspects

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn = 30100;
const int bound = 30001;
int gn, gm;
int f[maxn], cnt[maxn];
vector<int> v;

int getFather(int x) {
    if(x == f[x]) return x;
    else return f[x] = getFather(f[x]);
}

int main()
{
    int k, input;
    while(scanf("%d%d", &gn, &gm) == 2 && (gn || gm)) {
        for(int i = 0; i <= bound; i++) { f[i] = i; cnt[i] = 1; }
        for(int i = 0; i < gm; i++) {
            scanf("%d", &k);
            v.clear();
            for(int j = 0; j < k; j++) {
                scanf("%d", &input);
                v.push_back(input);
            }
            if(k==1) continue;
            else {
                int first = v[0];
                for(int t = 1; t < (int)v.size(); t++) {
                    int parent = getFather(first);
                    int parentx = getFather(v[t]);
                    if(parent == parentx) continue;
                    else {
                        cnt[parent] += cnt[parentx];
                        f[parentx] = parent;
                    }
                }
            }
        }
        int parent = getFather(0);
        printf("%d\n", cnt[parent]);
    }
    return 0;
}

POJ1611 The Suspects,布布扣,bubuko.com

POJ1611 The Suspects

原文：http://blog.csdn.net/achiberx/article/details/21463473