CodeForces 1167C News Distribution (并查集)

題意：每個人都屬于一個或多個集合，稱集合裡的人互相有關，輸出與每個人直接或間接有關的人數。

題解：并查集

Rank[]維護高度，這樣cnt[]就可以表示根的集合大小。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
const int maxn = 5e5 + 5;
int n, m, k, p, q;
int Parent[maxn], Rank[maxn], cnt[maxn], num;
int Find(int x) {
	return Parent[x] == x ? x : Parent[x] = Find(Parent[x]);
}
void Union(int x, int y) {
	int u, v, root;
	u = Find(x);
	v = Find(y);
	if (u == v) {
		return;
	}
	if (Rank[u] <= Rank[v]) {
		cnt[v] += cnt[u];
		root = Parent[u] = v;
		if (Rank[u] == Rank[v])
			Rank[v]++;
	}
	else {
		cnt[u] += cnt[v];
		root = Parent[v] = u;
	}
	//return root;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		cnt[i] = 1;
		Parent[i] = i;
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d", &k); k--;
		if (k < 0) continue;
		scanf("%d", &p);
		while (k--) {
			scanf("%d", &q);
			Union(q, p);
		}
	}
	for (int i = 1; i <= n; i++) {
		num = 0;
		printf("%d ", cnt[Find(i)]);
	}
	return 0;
}