并查集与字典树

并查集与字典树是两个"一句话就能说清、实现极短、用处极大"的结构：前者维护等价类（哪些元素在同一集合），后者检索前缀（哪些键有共同开头）。

并查集（Union-Find）

并查集维护不相交集合，支持两个操作：

find(x)： $x$ 所在集合的代表元；
union(x, y)：合并两个集合。

实现用一片森林：每个节点存父亲，代表元即根。

class DSU:
    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]]  # 路径压缩
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:      # 按秩合并
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

两个优化——路径压缩（find 时把沿途节点直接挂到根）与按秩合并（矮树挂到高树下）——把均摊代价降到反 Ackermann 函数级：

\Theta(\alpha(n)), \qquad \alpha(n) \le 4 \text{（对一切实际输入）}.

这是数据结构里最接近 $O(1)$ 的非平凡复杂度，且实现只有几行。

应用：Kruskal 最小生成树（判断加入的边是否成环）、连通分量、等价类维护、网络连通性。它的思想对应图的基本算法中的连通性，但比 DFS 更适合动态合并的场景。

字典树（Trie）

字典树把键按字符逐层存放，从根到节点的路径即一个键的前缀：

操作	哈希表	字典树
精确查找	$O(1)$ 期望	$O(L)$ （ $L$ 为键长）
前缀查询	不支持	$O(L)$
按序遍历	需要额外排序	天然有序
最坏情况	$O(n)$ （冲突）	$O(L)$ 稳定

字典树的核心优势是前缀：自动补全、拼写检查、IP 路由最长前缀匹配、统计以某前缀开头的词——这些是哈希表做不到的。

变体：

压缩字典树（radix tree）：合并单孩子链，减少空间；Linux 内核的页缓存与路由表用它；
AC 自动机：字典树 + 失配指针，多模式串匹配（→ 字符串算法）；
基数树：按固定宽度的"数字"（如 4 位）分支，IP 转发表的标准结构。

如何选择

动态等价类 / 合并连通性 → 并查集；
前缀相关查询 → 字典树；
只有精确查找、不需要有序 → 哈希表（→ 哈希表）；
需要有序 + 范围查询 → 平衡树（→ 二叉搜索树与平衡树）。

本章要点

并查集用森林实现：路径压缩 + 按秩合并把均摊代价降到 $\Theta(\alpha(n))$ ，实际即常数
并查集适合动态合并场景：Kruskal、连通分量、等价类
字典树的核心优势是前缀查询与天然有序；精确查找比哈希表慢（ $O(L)$ vs $O(1)$ ）
AC 自动机 = 字典树 + 失配指针，是多模式匹配的基础