05_并查集

并查集

什么是并查集？

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

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

核心优化

1. 路径压缩 (Path Compression)

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

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

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

时间复杂度

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

实现

1. 基础用法（函数式）

n = 5
parent = list(range(n))

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    px, py = find(x), find(y)
    if px != py:
        parent[px] = py

union(0, 1)
union(1, 2)
print(find(0) == find(2))  # True

2. 朋友圈/连通分量计数

def count_components(n, edges):
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py

    for u, v in edges:
        union(u, v)

    return len(set(find(i) for i in range(n)))

3. 类实现（推荐）

class DSU:
    """并查集 (Disjoint Set Union) - 带路径压缩 + 按秩合并"""

    def __init__(self, n: int = 0):
        self.init(n)

    def init(self, n: int):
        self.n = n
        self.cnt = n
        self.f = list(range(n))
        self.siz = [1] * n

    def find(self, x: int) -> int:
        while x != self.f[x]:
            self.f[x] = self.f[self.f[x]]   # 路径压缩（迭代版，防递归爆栈）
        return self.f[x]

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

    def merge(self, x: int, y: int) -> bool:
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.siz[x] < self.siz[y]:       # 按大小合并
            x, y = y, x
        self.f[y] = x
        self.siz[x] += self.siz[y]
        self.cnt -= 1
        return True

    def size(self, x: int) -> int:
        return self.siz[self.find(x)]

    def count(self) -> int:
        return self.cnt


# 竞赛输入输出模板
size, query_num = [int(i) for i in input().split()]
dsu = DSU(size)
for _ in range(query_num):
    q_type, u, v = [int(i) for i in input().split()]
    if q_type == 0:
        dsu.merge(u, v)
    else:
        print(1 if dsu.same(u, v) else 0)

应用场景

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