Okay, three, two, one, let's jam

507 并查集

3 min read

并查集

概念

定义：并查集（Union-Find Set）是一种用于处理不相交集合的合并及查询问题的数据结构。

核心思想：维护若干个不相交的集合，支持快速判断两个元素是否属于同一集合，以及合并两个集合。

支持的操作

1. Find(x)：查找操作

  • 功能：查找元素 x 所属集合的代表元素（根节点）
  • 用途：判断两个元素是否属于同一集合

2. Union(x, y)：合并操作

  • 功能：将元素 x 和 y 所在的两个集合合并为一个集合
  • 前提：x 和 y 不在同一集合中

3. MakeSet(x)：初始化操作

  • 功能：创建一个只包含元素 x 的新集合
  • 通常在初始化阶段批量执行

存储结构

数组表示法：

  • parent[i]：存储节点 i 的父节点
  • 根节点特征：parent[i] = i（自己指向自己）
  • 路径表示：从任意节点向上追溯可到达根节点

辅助数组（用于优化）：

  • rank[i]：节点 i 的秩（子树高度的上界）
  • size[i]：以节点 i 为根的子树大小

算法实现

基本实现

初始化：

MakeSet(x):
    parent[x] = x

查找操作：

Find(x):
    if parent[x] ≠ x:
        return Find(parent[x])
    return x

合并操作：

Union(x, y):
    rootX = Find(x)
    rootY = Find(y)
    if rootX ≠ rootY:
        parent[rootX] = rootY

时间复杂度：

  • Find 操作：O(h)，其中 h 为树的高度
  • Union 操作：O(h)
  • 最坏情况：树退化为链，h = O(n)

优化实现

1. 路径压缩（Path Compression）：

Find(x):
    if parent[x] ≠ x:
        parent[x] = Find(parent[x])  // 路径压缩
    return parent[x]
  • 效果：将查找路径上的所有节点直接指向根节点
  • 优势：后续查找操作时间复杂度接近 O(1)

2. 按秩合并（Union by Rank）：

Union(x, y):
    rootX = Find(x)
    rootY = Find(y)
    if rootX ≠ rootY:
        if rank[rootX] < rank[rootY]:
            parent[rootX] = rootY
        else if rank[rootX] > rank[rootY]:
            parent[rootY] = rootX
        else:
            parent[rootY] = rootX
            rank[rootX]++
  • 原则：将秩小的树合并到秩大的树上
  • 效果：控制树的高度，避免退化为链

3. 按大小合并（Union by Size）：

Union(x, y):
    rootX = Find(x)
    rootY = Find(y)
    if rootX ≠ rootY:
        if size[rootX] < size[rootY]:
            parent[rootX] = rootY
            size[rootY] += size[rootX]
        else:
            parent[rootY] = rootX
            size[rootX] += size[rootY]

优化后时间复杂度：

  • 单次操作：O(α(n))，其中α为阿克曼函数的反函数
  • 实际意义：α(n) ≤ 5 对于所有实际应用，近似为常数时间
  • m 次操作总时间：O(m·α(n))

空间复杂度：O(n)

Graph View

Backlinks