目录

  1. 并查集的基本概念
  2. 并查集的基本操作
  3. 时间复杂度分析
  4. 代码示例（伪代码）
  5. 参考资料

1. 并查集的基本概念

并查集是一种用于处理动态连通性问题的数据结构，主要用于管理元素的集合划分。它支持高效地合并两个集合（Union）和查询两个元素是否属于同一集合（Find）。

  • 核心思想：用树形结构表示集合，每个节点指向其父节点，根节点代表集合。
  • 应用场景：图的连通性、最小生成树（如 Kruskal 算法）、网络连通性分析等。

2. 并查集的基本操作

并查集支持以下两种基本操作：

  1. 查找（Find）：
  • 找到元素所在集合的代表元素（通常是树的根节点）。
  • 方法：从元素出发，沿着父节点指针向上，直到找到根。
  1. 合并（Union）：
  • 将两个集合合并为一个。
  • 方法：将一个集合的根节点指向另一个集合的根节点。

示例

初始：元素 1, 2, 3, 4 各自独立。

  • Union(1, 2)：合并 1 和 2，树为 1 ← 2。
  • Union(3, 4)：合并 3 和 4，树为 3 ← 4。
  • Union(2, 3)：合并 2 和 3 所在集合，树为 1 ← 2 ← 3 ← 4。
  • Find(4)：返回根节点 1，表示 4 属于集合 1。

3. 时间复杂度分析

基础实现的复杂度：

  • 初始化：O(n)，n 为元素个数。
  • 查找（Find）：O(h)，h 为树高，最差 O(n)（退化为链表）。
  • 合并（Union）：O(h)，依赖查找操作。
  • 总复杂度（m 次操作）：O(m * n)，m 为操作次数。

优化后（路径压缩 + 按秩合并，见后续优化内容）：

  • 单次操作接近 O(1)，总复杂度为 O(m * α(n))，其中 α(n) 是阿克曼函数的反函数，实际可视为常数。

4. 代码示例（伪代码）

class UnionFind:
    parent[]      // 父节点数组
    size          // 元素总数

    // 初始化
    function init(n):
        size = n
        for i = 0 to n-1:
            parent[i] = i    // 每个元素初始为独立集合

    // 查找
    function find(x):
        while parent[x] != x:
            x = parent[x]
        return x

    // 合并
    function union(x, y):
        rootX = find(x)
        rootY = find(y)
        if rootX != rootY:
            parent[rootX] = rootY

5. 参考资料

如果你需要优化版本（如路径压缩或按秩合并）的讲解，或特定语言实现，请告诉我！