1107 Social Clusters (30分)/并查集

题目描述

分析

hobby存放某个爱好的代表人物，即以此爱好为集合的根节点。这里以father[i]<0表示i为根节点，因此初始化时将father[]数组全部初始化为-1。由于本题数据量小，路径压缩、按秩归并的作用并不大。

#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
int hobby[1005], father[1005];
int find(int x) {
	while (father[x]>0) {
		x = father[x];
	}
	return x;
}
void Union(int a, int b) {
	int A = find(a), B = find(b);
	if (A != B) { //按秩归并
		if (father[A]<father[B]) {
			father[A] += father[B]; //人数的计算
			father[B] = A;
		}
		else {			
			father[B] += father[A];
			father[A] = B;
		}
	}
}
int main() {
#ifdef ONLINE_JUDGE
#else
	freopen("1.txt", "r", stdin);
#endif	
	int n; cin >> n;
	memset(father, -1, sizeof(father)); //全部初始化为-1
	for (int i = 1; i <= n; i++) {
		int k; scanf("%d:", &k);
		while (k--) {
			int t; scanf("%d", &t);
			if (hobby[t] == 0) hobby[t] = i;
			else Union(i, hobby[t]);
		}
	}
	vector<int> ans;
	for (int i = 1; i <= n; i++) {
		if (father[i] < 0) { //i为根节点
			ans.push_back(father[i]); //father的绝对值表示社群中的人数
		}
	}
	cout << ans.size() << endl;
	sort(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++) {
		if (i != 0) printf(" ");
		printf("%d", -ans[i]);
	}
	return 0;
}