hub并查集
并查集题型：怎么识别、怎么讲、怎么练
并查集最适合那种“不是只遍历一次图，而是不断做合并”的问题。只要题目反复问“现在这两个东西是否属于同一连通块”，DSU 往往就是对的。
覆盖题量
30+
推荐起手
先把元素映射成索引，再写 DSU。
高频误区
忘记路径压缩，复杂度退化很严重。
什么时候该想到这个模式
题目重点是多次合并之后的连通性。
你需要判断加边后是否产生环。
更关心连通块个数，而不是具体路径。
下手前的检查清单
先把元素映射成索引，再写 DSU。
find 做路径压缩，union 做按秩或按大小合并。
明确一次成功合并对答案意味着什么。
如果 union 可能失败，统计连通块时要格外小心。
真正适合面试表达的解题步骤
1
初始化时每个节点都是自己的父节点。
2
find 时做路径压缩，保证后续查询足够快。
3
union 只合并根节点，不合并原节点。
4
union 失败不是报错，而是题目信息。
5
最终答案要么来自成功合并次数，要么来自根节点去重。
常见变体
连通性判断
判断一系列合并后两个点是否连通。
环检测
如果 union 失败且根相同，通常意味着新边形成了环。
连通块计数
跟踪若干次合并后还剩多少连通块。
模板预览
Python公开预览
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.rank[pa] < self.rank[pb]:
pa, pb = pb, pa
self.parent[pb] = pa
if self.rank[pa] == self.rank[pb]:
self.rank[pa] += 1
return True
更像真实刷题路径的推荐题单
这组题不是随机罗列，而是按“先建立识别感，再补关键变体，最后上强度”去排，适合真的拿来做一轮 pattern 复习。
高频坑点
warning
忘记路径压缩，复杂度退化很严重。
warning
直接合并原节点而不是根节点。
warning
输入如果是字符串或邮箱，没先做好映射。
warning
统计连通块时没处理重复边或重复 union。
练习顺序建议
1
先做冗余连接和省份数量。
2
再做邮箱/账户合并类问题。
3
然后补方程可满足性或图分组问题。
4
最后把并查集和排序结合到最小生成树题里。