05_Disjoint Set Union 并查集

并查集

什么是并查集？

并查集（Disjoint Set Union，DSU）数据结构，也称为并查集或联合-查找数据结构，允许你向图中添加边，并测试图中两个顶点是否相连。

由于实现非常简单，你可能更倾向于使用它来代替 DFS 计算连通分量。

---

实现

class DisjointSets:
    def __init__(self, size: int) -> None:
        self.parents = [i for i in range(size)]
        self.sizes = [1 for _ in range(size)]

    def find(self, x: int) -> int:
        """返回 x 所在集合的代表节点"""
        if self.parents[x] == x:
            return x
        self.parents[x] = self.find(self.parents[x])  # 路径压缩
        return self.parents[x]

    def unite(self, x: int, y: int) -> None:
        """合并 x 和 y 所在的集合"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        # 按秩/大小合并
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]

    def connected(self, x: int, y: int) -> bool:
        """检查 x 和 y 是否在同一集合中"""
        return self.find(x) == self.find(y)

---

核心优化

1. 路径压缩 (Path Compression)

在 find 操作中，将路径上的所有节点直接指向根节点，大大加快后续查询。

2. 按秩合并 (Union by Rank/Size)

总是将较小的树合并到较大的树下，保持树的平衡性。

---

时间复杂度

并查集的各种操作的时间复杂度均为 $O(\alpha(N))$，其中 $\alpha$ 是反阿克曼函数，在实际应用中近似为常数。

---

示例 - 并查集 (Union Find)

Focus Problem: 在继续之前，请尽力解决这个问题！

题目描述

我们需要处理两类操作：

• 合并两个顶点所在的集合
• 查询两个顶点是否在同一连通分量中

不用并查集

如果没有并查集，我们需要用邻接表表示图，并使用泛洪填充来计算连通分量。这种方法需要 $O(NQ)$ 时间，这太慢了。

使用并查集

通过使用并查集数据结构，我们可以使用其方法来合并顶点，并仅用 $O(\alpha(N))$ amortized 时间检查两个顶点是否在同一个连通分量中。

这将整体时间复杂度降低到 $O(Q \alpha(N))$，这是一个显著的改进，并使我们能够通过所有测试用例。

代码实现

class DisjointSets:
    def __init__(self, size: int) -> None:
        self.parents = [i for i in range(size)]
        self.sizes = [1 for _ in range(size)]

    def find(self, x: int) -> int:
        if self.parents[x] == x:
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def unite(self, x: int, y: int) -> None:
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


size, query_num = [int(i) for i in input().split()]

dsu = DisjointSets(size)
for _ in range(query_num):
    q_type, u, v = [int(i) for i in input().split()]
    if q_type == 0:
        dsu.unite(u, v)
    else:
        print(1 if dsu.connected(u, v) else 0)

---

应用场景

1. 连通分量计算 - 判断图中两点是否连通
2. 集合合并 - 合并若干集合
3. 最近公共祖先 (LCA) - 在树中求 LCA
4. Kruskal 最小生成树 - 边的集合合并
5. 贪心算法 - 某些贪心问题的辅助数据结构

---

经典问题

题目	难度	描述
Union Find	Easy	并查集基础应用