题目定位
这是最纯粹的并查集题：如果两个点本来就属于同一集合，那么下一条边就是冗余边。
关键观察
第一条两端点已连通的边，就是造成成环的那条边。
目标复杂度
O(n alpha(n)) / O(n)
这题的解法思路怎么拆
1
这是最纯粹的并查集题：如果两个点本来就属于同一集合，那么下一条边就是冗余边。
2
第一条两端点已连通的边，就是造成成环的那条边。
3
初始化时每个节点都是自己的父节点。
4
find 时做路径压缩，保证后续查询足够快。
参考实现
Python# Generic pattern template
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
常见坑点
warning
直接比较 parent 而不是比较根。
warning
DSU 初始化的节点范围不对。
高频追问
为什么这里 DSU 比每条边都 DFS 更自然？
如果是有向边，题目会有什么变化？
继续刷相关题
先把 并查集 这个模式刷成体系，再去做更难变体。