S-L04 集合与森林·并查集¶

#include <bits/stdc++.h>
using namespace std;

// 并查集：路径压缩 + 按大小合并，单次操作均摊近似 O(alpha(n))
struct DSU {
    vector<int> fa, sz;
    DSU(int n) : fa(n), sz(n, 1) { iota(fa.begin(), fa.end(), 0); }
    int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
    bool merge(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;          // 已在同一集合
        if (sz[x] < sz[y]) swap(x, y);
        fa[y] = x; sz[x] += sz[y];
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
};