并查集算法详解

并查集算法简介

并查集（Disjoint Set Union，DSU）是一种用于管理元素分组的数据结构，支持两种核心操作：

  • 查找（Find）：确定某个元素属于哪个集合（通常返回集合的代表元素）。
  • 合并（Union）：将两个集合合并为一个集合。

常用于解决动态连通性问题，如网络连接、图的连通分量计算等。

核心实现方法

路径压缩优化（Find）

在查找时，将节点的父节点直接指向根节点，缩短后续查找路径。

`int find(int x, vector& parent) {
if (parent[x] != x) {
parent[x] = find(parent[x], parent); // 路径压缩
}
return parent[x];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

##### 按秩合并（Union）

合并时，将较小的树（按秩或大小）合并到较大的树下，避免树过高。


`void unionSets(int x, int y, vector<int>& parent, vector<int>& rank) {<!-- -->
    int rootX = find(x, parent);
    int rootY = find(y, parent);
    if (rootX != rootY) {<!-- -->
        if (rank[rootX] > rank[rootY]) {<!-- -->
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {<!-- -->
            parent[rootX] = rootY;
        } else {<!-- -->
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

时间复杂度分析

未优化版本
  • Find：最坏情况下为 $O(n)O(n)$O(n)（退化为链表）。
  • Union：依赖 Find 操作，同样为 $O(n)O(n)$O(n)。
带路径压缩和按秩合并

通过优化，均摊时间复杂度接近常数：

  • Find 和 Union：均摊时间复杂度为 $O(α(n))O(\alpha(n))$O(α(n))，其中 $α(n)\alpha(n)$α(n) 是反阿克曼函数，增长极其缓慢（对于实际应用可视为常数）。
反阿克曼函数 $α(n)\alpha(n)$α(n)

定义为阿克曼函数 $A(m,n)A(m, n)$A(m,n) 的逆，满足：

$A(α(n),n)≤log⁡nA(\alpha(n), n) \leq \log n$A(α(n),n)≤logn

对于任何实际输入（如 $n≤221019729n \leq 2^{2^{10^{19729}}}$n≤221019729），$α(n)≤4\alpha(n) \leq 4$α(n)≤4。

应用场景

  • 动态连通性问题：判断图中两个节点是否连通。
  • 最小生成树（Kruskal算法）：按边权排序后使用并查集管理连通性。
  • 社交网络分组：快速合并用户关系集合。

完整代码示例

`#include
using namespace std;

class DSU {
private:
vector parent, rank;
public:
DSU(int n) : parent(n), rank(n, 0) {
for (int i = 0; i < n; ++i) parent[i] = i;
}

int find(int x) {<!-- -->
    if (parent[x] != x) {<!-- -->
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unionSets(int x, int y) {<!-- -->
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {<!-- -->
        if (rank[rootX] > rank[rootY]) {<!-- -->
            parent[rootY] = rootX;
        } else {<!-- -->
            parent[rootX] = rootY;
            if (rank[rootX] == rank[rootY]) rank[rootY]++;
        }
    }
}

};
```