什么是并查集（Union-Find），它在哪里使用？

Question

Accepted Answer

**Union-Find**（Disjoint Set Union）追踪将元素划分为**互不相交的集合**，并支持两个接近 O(1) 的操作：**find**（x 在哪个集合中？）和 **union**（合并两个集合）。它在**连通性**查询中表现出色。

## 基本思想

每个集合是一棵以代表性根节点为首的树。通过**路径压缩**和**按秩/大小合并**，操作以接近常数的**摊销**时间运行（逆阿克曼函数，α(n)）。

## 示例

```python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # compress
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # already connected
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra           # attach smaller under larger
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True
```

## 复杂度

- **find / union：** O(α(n)) ≈ O(1) 摊销。**空间：** O(n)。

## 应用场景

- **Kruskal 最小生成树** — 添加边时的环检测。
- **连通分量** / 动态连通性。
- **无向图中的环检测**。
- **渗流**、图像分割、账户/网络合并。

## 常见陷阱

没有路径压缩和按秩合并，树会退化为 O(n) 的链。它不支持集合的高效**分割**。

## 为什么这很重要

并查集以几乎零成本回答