POJ 1611 The Suspects（并查集，记录集合总数）

并查集

本题要点：
1、sum[i] 表示以i点为父节点的集合总数， 初始化的时候，
每个点以自身为父节点，sum[i] = 1;
在合并操作的时候，fa[fay] =fax;
sum[fax] += sum[fay];

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 30010;
int n, m;
int fa[MaxN];
int sum[MaxN];	//sum[i] 表示以i点为父节点的集合总数int get(int x)
{
    if(fa[x] == x)return x;return fa[x] = get(fa[x]);
}void merge(int x, int y)
{
    int fax = get(x);int fay = get(y);if(fax != fay){
    fa[fay] =fax;sum[fax] += sum[fay];}
}void init()
{
    for(int i = 0; i < n; ++i){
    	fa[i] = i;sum[i] = 1;}
}int main()
{
    int k;while(scanf("%d%d", &n, &m) != EOF){
    if(0 == n && 0 == m)break;init();for(int x = 0; x < m; ++x){
    int one, two;scanf("%d", &k);scanf("%d", &one);k--;while(k--){
    scanf("%d", &two);merge(one, two);}}printf("%d\n", sum[get(0)]);}return 0;
}/* 100 4 2 1 2 5 10 13 11 12 14 2 0 1 2 99 2 200 2 1 5 5 1 2 3 4 5 1 0 0 0 *//* 4 1 1 */