POJ1611 The Suspects【并查集】

The Suspects

題意： n個人被分為m個小團體，要求輸出編号0的人所在團體的總人數。

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 3e4 + 10;
int n, m;
int s[N], num[N];

void init() {	for(int i = 0; i < N; i++) s[i] = i, num[i] = 1;}
int find(int x){ return s[x] == x ? x : s[x] = find(s[x]);}
void un(int a, int b) {
	int sa = find(a), sb = find(b);
	if(sa != sb){
		s[sa] = sb;
		num[sb] += num[sa];
	}	
}

void run() {
	init();
	for(int i = 0; i < m; i++) {
		int x, v, pre;
		scanf("%d%d", &x, &pre);
		for(int i = 1; i < x; i++) {
			scanf("%d", &v);
			un(pre, v);
		}
	}
	printf("%d\n", num[find(0)]);
}

int main() {
	while(~scanf("%d%d", &n, &m) && (n || m)) run();
	return 0;
}