并查集

适用场景

并查集（Disjoint Set Union，DSU）维护若干个不相交集合，支持两种操作：

unite(x, y)：合并 $x$ 和 $y$ 所在的集合；
find(x)：查询 $x$ 所在集合的代表元，从而判断两个元素是否连通。

遇到下面这些问题时可以考虑并查集：

无向图中只加边、不删边的连通性查询；
Kruskal 最小生成树中判断一条边是否成环；
等价关系的合并，例如" $a = b$ "" $b = c$ "这类约束；
离线处理时把”删边”倒过来变成”加边”。

如果需要删边，普通并查集做不到，要用可撤销并查集配合线段树分治，或者使用 Link-Cut Tree。

核心思路

每个集合用一棵有根树表示，根节点就是代表元，fa[x] 记录 $x$ 的父节点。find 沿父指针走到根，unite 把一棵树的根挂到另一棵树的根下面。

朴素实现可能退化成一条链，单次操作 $O(n)$ 。有两个优化：

路径压缩：find 时把经过的节点直接（或隔一个）挂到更靠近根的位置，让树变矮。模板中的 x = fa[x] = fa[fa[x]] 是”路径减半”，效果和递归压缩相同，但不用递归，不会爆栈。
按大小合并（启发式合并）：把小集合的根挂到大集合的根下面。单独使用时，树高不超过 $O(\log n)$ ，因为一个节点每往下沉一层，它所在集合的大小至少翻倍。

复杂度

两个优化同时使用时， $m$ 次操作的总时间是 $O(m\,\alpha(n))$ 。这里的 $\alpha$ 是反阿克曼函数，在任何实际规模下都不超过 $4$ ，可以视为常数。

只用路径压缩时，均摊复杂度是 $O(\log n)$ ，竞赛中通常也够用。

空间复杂度为 $O(n)$ 。

模板

// 并查集（Disjoint Set Union）：路径压缩 + 按大小合并
struct DSU {
    vector<int> fa, sz;  // fa: father 父节点, sz: size 集合大小

    DSU(int n) : fa(n), sz(n, 1) { iota(fa.begin(), fa.end(), 0); }

    // 返回 x 所在集合的代表元，并做路径压缩
    int find(int x) {
        while (x != fa[x]) x = fa[x] = fa[fa[x]];
        return x;
    }

    // 判断 x、y 是否在同一集合
    bool same(int x, int y) { return find(x) == find(y); }

    // 合并 x、y 所在集合；已在同一集合时返回 false
    bool unite(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;
    }

    // 返回 x 所在集合的大小
    int size(int x) { return sz[find(x)]; }
};

模板题

Library Checker 的题目格式是：先输入 $N, Q$ ，接着 $Q$ 行 t u v。t = 0 表示合并，t = 1 表示询问 $u, v$ 是否连通，连通输出 1，否则输出 0。

void solve() {
    int n, q;
    cin >> n >> q;
    DSU d(n);
    while (q--) {
        int t, u, v;
        cin >> t >> u >> v;
        if (t == 0) d.unite(u, v);
        else cout << d.same(u, v) << '\n';
    }
}

常见坑

递归写法爆栈：递归的 find 在第一次压缩一条长链时，递归深度可能达到 $10^6$ 。用模板中的迭代写法，或保证按大小合并。
忘记初始化：fa[i] = i 必须在使用前完成，多组数据时要重新初始化。
合并时没有先找根：写成 fa[x] = y 而不是 fa[find(x)] = find(y)，会破坏树结构。
集合大小只存在根上：sz[x] 只有当 $x$ 是根时才有意义，查询前要先 find。

扩展

带权并查集：在边上维护到父节点的”势能差”，可以处理” $a$ 比 $b$ 大 $3$ “这类约束。
可撤销并查集：只按大小合并、不做路径压缩，用栈记录修改以便回滚。
扩展域并查集：把每个元素拆成”自己”和”敌人”两个节点，用来处理二分图或”敌人的敌人是朋友”这类关系。

并查集

适用场景

核心思路

复杂度

模板

模板题

常见坑

扩展

延伸阅读