题型识别#

核心操作只有两个：find 找代表节点，union 合并两个集合。路径压缩能让后续查询更快。

遇到类似题时，我会先写一句话解释输入、输出和约束，再决定用什么结构。只要这一步说不清，直接写代码大概率会在边界条件上出错。

核心写法#

1
class DSU:
2
    def __init__(self, n):
3
        self.parent = list(range(n))
4

5
    def find(self, x):
6
        if self.parent[x] != x:
7
            self.parent[x] = self.find(self.parent[x])
8
        return self.parent[x]
9

10
    def union(self, a, b):
11
        ra, rb = self.find(a), self.find(b)
12
        if ra != rb:
13
            self.parent[rb] = ra

边界样例#

• 空输入或只有一个元素时，答案应该是什么。
• 元素重复时，比较关系是否仍然成立。
• 结果需要下标、长度、数量，还是具体路径。
• 时间复杂度能不能从每个元素处理次数解释出来。

复盘#

复盘时要注意并查集不擅长删除边。如果题目有频繁删除关系，要考虑其他结构或离线处理。

最小验收样例#

我会至少准备三个样例：一个普通样例，一个边界样例，一个专门卡比较条件的样例。算法代码最怕只过了题目给的样例，却没有覆盖空输入、重复元素或极端顺序。

写完后不要只看答案，还要能解释每一步状态为什么变化。只要能把状态变化讲清楚，换一个题面时就不容易机械套错模板。

小结#

并查集处理连通关系 的练习重点，是把固定套路拆成可解释的判断。能说明为什么这样维护状态，才算真正掌握。