CF771A. Bear and Friendship Condition 题解 并查集

题目链接：https://codeforces.com/problemset/problem/771/A

视频讲解：https://www.bilibili.com/video/BV1tZ1FYPELp/?p=6

题目大意：判断一个无向图中的每个连通块是否都是一个完全图。

首先我们可以用并查集维护每个连通块的大小。

其次，我们可以开一个 \(cnt_i\) 表示以节点 \(i\) 为根的连通块中包含多少条边。

则对于每个连通块的根节点 \(i\)，必须满足 \(\frac{ sz_i \times (sz_i - 1) }{2} = cnt_i\) 才是 YES；否则，是 NO。（这里 \(sz_i\) 表示以 \(i\) 为根的连通块的大小，即这个连通块中的节点个数）

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1.5e5 + 5;
int n, m, f[maxn], sz[maxn], cnt[maxn];
struct Edge {
	int u, v;
} e[maxn];

void init() {
	for (int i = 1; i <= n; i++)
		f[i] = i, sz[i] = 1;
}

int find(int x) {
	return x == f[x] ? x : f[x] = find(f[x]);
}

void funion(int x, int y) {
	int a = find(x), b = find(y);
	if (a != b) {
		f[b] = a;
		sz[a] += sz[b];
	}
}

int main() {
	scanf("%d%d", &n, &m);
	init();
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &e[i].u, &e[i].v);
		funion(e[i].u, e[i].v);
	}
	for (int i = 0; i < m; i++) {
		cnt[find(e[i].u)]++;
	}
	for (int i = 1; i <= n; i++) {
		if (i == find(i)) {
			if ((long long)sz[i] * (sz[i] - 1) / 2 != cnt[i]) {
				puts("NO");
				return 0;
			}
		}
	}
	puts("YES");
	return 0;
}