什么是带有路径压缩和按秩合并的不相交集合(union-find)结构？

Question

IT Interview Practice · Accepted Answer

**disjoint-set** (union-find) 追踪分割成不重叠组的元素，并在**近乎常数时间**内回答"**这两个是否在同一组？**"和"**合并两个组**"的问题。使用**路径压缩**和**按秩合并**，两个操作都在**O(α(n))**时间内运行——实际上是 O(1)（α 是反 Ackermann 函数）。

## 它如何工作

每个集合是一棵树；**根**是集合的代表。`find` 走向根；`union` 将一个根链接到另一个根。

```text
find(x): follow parents to the root
union(a,b): attach the shorter tree under the taller (by rank)
path compression: after find, point nodes DIRECTLY at the root
   before:  a->b->c->root      after:  a->root, b->root, c->root
```

## Code

```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    def find(self, x):                       # path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # halve path
            x = self.parent[x]
        return x
    def union(self, a, b):                   # union by rank
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True
```

| 操作 | 时间复杂度（应用两种优化） |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## 常见用途

- **Kruskal 最小生成树** — 合并分量而不形成环。
- **连通分量**在图或网格中。
- **动态连通性**和网络/渗透问题。

## 为什么这很重要

Union-find 解决了分组和连通性问题，否则需要重复的 O(n) 图遍历，将其压缩为近乎 O(1) 的每次查询。

无论何时需要增量合并集合并测试连通性，它都是首选工具——这是一个常见的高级面试话题。

它如何工作

Code

常见用途

为什么这很重要

相关问题