B - The Suspects POJ - 1611

基并查集

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 3e4+100;
int n, m;
int fa[maxn], cnt[maxn];

void init() {
	memset(cnt, 0, sizeof(cnt));
	for(int i = 0; i < n; i++) fa[i] = i, cnt[i] = 1;
}

int find(int x) {
	if(fa[x] == x) return x;
	else return fa[x] = find(fa[x]);
}

void Union(int x, int y) {
	int xx = find(x), yy = find(y);
	if(xx == yy) return ;
	if(cnt[xx] > cnt[yy]) swap(xx, yy);
	fa[xx] = yy; cnt[yy] += cnt[xx];
	return ; 
}

int main() {
//	freopen("test.in", "r", stdin);
	while(~scanf("%d%d", &n ,&m) && n+m) {
		init();
		for(int i = 0; i < m; i++) {
			int k; scanf("%d", &k);
			int s, tmp, ss;
			for(int i = 1; i <= k; i++) {
				if(i == 1) {
					scanf("%d", &s);
				}
				else {
					scanf("%d", &tmp);
					if(find(s) != find(tmp)) Union(s, tmp);
				};
			}
		}
//		for(int i = 0; i < n; i++) printf("cnt[%d]=%dn", i, cnt[i]);
		printf("%dn", cnt[find(0)]);
	}
	return 0;
} 

最后

以上就是无辜菠萝为你收集整理的B - The Suspects POJ - 1611B - The Suspects POJ - 1611的全部内容，希望文章能够帮你解决B - The Suspects POJ - 1611B - The Suspects POJ - 1611所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。