Atcoder Beginning Contest 292 D - Unicyclic Components (并查集)

思路:

一个连通块是否点数 == 边数:

并查集维护一个个连通块, 点数就是连通块的点数, 边数 == 连通块中每个点的度数的和 / 2

注意:

合并完之后,可能有一些点并没有连到根上, find(i)路径压缩只会将i这个点以及向上到根的点连到根上, 但是i这个点下面的点还是之前的样子,并没有压缩.

所以当用到某个点以及其根节点时, 需要find一下, 不然f[i]可能只是i这个点的父节点, 但不是他们所在连通块的根节点.

#include<bits/stdc++.h>
using namespace std;
#define endl "
"
#define x first
#define y second
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
const int inf = 0x3f3f3f3f;
const ll infinf = 0x3f3f3f3f3f3f3f3f;

const int N = 2e5 + 10;
int f[N], deg[N];
vector<int> res[N];

int find(int x) {
    if (x != f[x]) f[x] = find(f[x]);
    return f[x];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) f[i] = i;

    // 并查集统计连通性,然后存储每个点的入度和出度,最后一个连通块的边数就是块中的点数的度数之和 / 2
    int x, y;
    for (int i = 1; i <= m; i ++) {
        cin >> x >> y;
        deg[x] ++; deg[y] ++;
        f[find(x)] = find(y);
    }

    set<int> s;
    for (int i = 1; i <= n; i ++) {
// 每个点的根节点需要再find一下,因为合并过程中可能有些点并没有连到根上
        f[i] = find(i); 
        res[f[i]].push_back(i);
        s.insert(f[i]);
    }

    for (auto it = s.begin(); it != s.end(); it ++) {
        ll point = res[*it].size(), sum = 0;

        for (int i = 0; i < res[*it].size(); i ++) sum += deg[res[*it][i]];

        if (point != sum / 2) {
            cout << "No";
            return 0;
        }
    }

    cout << "Yes";

    return 0;
}