「学习笔记」并查集

真的有必要说吗？

直接上封装好的模板吧，包含路径压缩和按秩合并。

struct union_find_set {
    int fa[N], siz[N];

    int &operator [] (const int& x) {
        return fa[x];
    }

    void reset() {
        for (int i = 1; i <= n; ++ i) {
            fa[i] = i;
            siz[i] = 1;
        }
    }

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

    void Union(int x, int y) {
        int fx = find(x), fy = find(y);
        if (siz[fx] <= siz[fy]) {
            swap(fx, fy);
        }
        fa[fy] = fx;
        siz[fx] += siz[fy];
    }
} ufs;