LC684Medium无向图并查集判环路径压缩

冗余连接

每加入一条边前，先问它的两个端点是否已经通过旧边连通：若 find 得到同一个根，新边会把既有路径闭合成环。

题目是什么

一棵树多加了一条无向边，找出删掉后仍能恢复成树的那条边。

解决什么问题

在按顺序加入边的过程中，高效判断两端是否早已连通。

核心结论

异根就 union；同根说明旧图已有路径，当前边闭合环，立即返回。

01交互算法精讲

先说结论：这道题到底解决什么

按顺序加入一条无向边之前，怎样用两个端点的最终根判断旧图中是否已经存在路径，并证明当前边会不会闭合成环？

中心结论：异根就 union；同根说明旧图已有路径，当前边闭合环，立即返回。

读完必须能回答

1.为什么必须比较 `find(u)` 与 `find(v)`，不能直接比较 parent[u] 与 parent[v]？
2.为什么两个端点同根时，当前边一定是冗余边？
3.为什么按输入顺序返回第一次同根边，满足题目要求的靠后候选？

02交互算法精讲

完整题目与题意拆解

给定一个包含 n 个节点的无向图。它原本是一棵树，后来额外加入了一条边。返回一条可以删除、使图重新成为树的边。

若存在多个可选答案，返回在输入 edges 中最后出现的那一条。节点编号从 1 开始。

• 图是无向图，原结构为树加一条边。
• 树本来连通且无环，多一条边后恰好产生一个环。
• 需要遵守输入顺序选择答案。

输入：edges = [[1,2],[1,3],[2,3]]
输出：[2,3]
解释：旧边已经让 2 通过 1 到达 3，再加入 [2,3] 会闭合三角环。

冗余边不是“看起来多余”的边，而是加入时两端已经通过此前边连通的那条边。旧路径加上新边，必然形成一个环。

并查集维护当前已经处理的边所形成的连通分量。find(x) 返回 x 所属集合的代表根，union 合并两个不同集合。

必须比较 find(u) 与 find(v)，不能只比较 parent[u]、parent[v]；parent 可能只是中间父节点，不一定是最终根。

动画 1 · 题意扫描

先看树多一条边怎样形成唯一环

观察三条边的输入顺序，以及第三条边加入前后图结构发生的变化。

Step 1/20%

输入边按顺序处理

root 1

root 2

root 3

[1,2] → [1,3] → [2,3]

原树多出一条边后出现环

发生了什么: 输入依次是 [1,2]、[1,3]、[2,3]，最终三条边围成一个环。
为什么: 树已有 n-1 条边且连通，再加一条边会在唯一旧路径上闭合环。
下一步: 先让每个节点成为自己的集合根。

当前状态

nodes / edges

3 / 3

当前 Go 代码

1func findRedundantConnection(edges [][]int) []int {2    parent := make([]int, len(edges)+1)3    for i := range parent { parent[i] = i }4    var find func(int) int5    find = func(x int) int {6        if parent[x] != x {7            parent[x] = find(parent[x])8        }9        return parent[x]10    }11    for _, edge := range edges {12        rootU, rootV := find(edge[0]), find(edge[1])13        if rootU == rootV {14            return edge15        }16        parent[rootV] = rootU17    }18    return nil19}

看完带走：冗余边不是视觉上最长的边，而是加入时两端已经通过旧边连通的边。

03交互算法精讲

第一层方案：暴力做法

维护已接纳边的邻接表。处理 edge=[u,v] 前，用 DFS 检查旧图中是否已有 u→v 路径；有则 edge 冗余，否则加入邻接表。

这个思路直接体现正确性，但每条边可能遍历 O(n) 节点与边，总体最坏 O(n²)。

for edge [u,v]:
  if reachable(u,v): return edge
  graph.add(edge)

并查集没有改变判断问题，只是把 reachable(u,v) 优化成 find(u)==find(v)。

动画 2 · 暴力重复

逐边 DFS 可达查询重复在哪里

每处理一条边都要问旧图是否已有路径；前两次结果会被下一次搜索重新走过。

Step 1/30%

检查 [1,2]

root 1

root 2

root 3

find(1)=1 != find(2)=2

边 [1,2] 两端根不同

发生了什么: find(1)=1，find(2)=2，旧图中 1 与 2 尚未连通。
为什么: 根不同表示属于不同连通分量，加入这条边不会形成环。
下一步: 接纳边 [1,2] 并合并两个根。

当前状态

rootU / rootV

1 / 2

当前 Go 代码

1func findRedundantConnection(edges [][]int) []int {2    parent := make([]int, len(edges)+1)3    for i := range parent { parent[i] = i }4    var find func(int) int5    find = func(x int) int {6        if parent[x] != x {7            parent[x] = find(parent[x])8        }9        return parent[x]10    }11    for _, edge := range edges {12        rootU, rootV := find(edge[0]), find(edge[1])13        if rootU == rootV {14            return edge15        }16        parent[rootV] = rootU17    }18    return nil19}

看完带走：并查集没有改变判环问题，只把 repeated reachable 查询压缩成 find 比较。

优化方向：并查集把历史连通关系压缩成 parent 森林。查询两点是否同集合和合并集合都接近常数时间。

04交互算法精讲

整体地图：先做什么，再做什么

先把暴力判断写清楚：处理边 [u,v] 前，在已经接纳的旧边中搜索是否存在 u 到 v 的路径。有路径时再加新边会闭环，没有路径时新边安全。

并查集只是在优化这次可达性查询。parent 森林把每个连通分量压缩到一个代表根；两个最终根相同等价于旧图中已经连通，根不同则执行 union。

• 初始化：每个节点各自是一个集合。
• 查询：对当前边两端执行 find。
• 决策：同根返回，异根合并后继续。

判断必须发生在 union 之前。先合并会让任何边的两端都变成同根，从而丢失“加入前是否已连通”的信息。

05交互算法精讲

parent 与最终根到底有什么区别

parent[x] 只表示并查集森林中 x 的直接父节点，它可能仍然指向另一个中间节点。`find(x)` 会沿 parent 链一直走到满足 parent[root]==root 的代表节点。

同一个连通分量中的节点可能拥有不同的直接 parent，但最终根相同。路径压缩在 find 返回时把中间节点直接连向根，缩短以后查询的路径，却不改变集合成员关系。

parent[4]=3, parent[3]=1, parent[1]=1
parent[4] != parent[2] 不能说明不连通
find(4)=1, find(2)=1 才说明属于同一分量

并查集比较的是集合代表，不是数组中眼前的一跳。

动画 3 · 核心概念

从 parent 一跳走到最终集合根

观察独立集合、第一次合并和第二次合并后，直接 parent 与最终 root 如何变化。

Step 1/40%

并查集初始化

root 1

root 2

root 3

parent

1→12→23→3

parent=[0,1,2,3]

每个节点一开始都是独立集合

发生了什么: 初始化 parent[1]=1、parent[2]=2、parent[3]=3。
为什么: 还没有处理任何边，节点之间尚未建立连通关系。
下一步: 对第一条边 [1,2] 的两端执行 find。

当前状态

components

当前 Go 代码

1func findRedundantConnection(edges [][]int) []int {2    parent := make([]int, len(edges)+1)3    for i := range parent { parent[i] = i }4    var find func(int) int5    find = func(x int) int {6        if parent[x] != x {7            parent[x] = find(parent[x])8        }9        return parent[x]10    }11    for _, edge := range edges {12        rootU, rootV := find(edge[0]), find(edge[1])13        if rootU == rootV {14            return edge15        }16        parent[rootV] = rootU17    }18    return nil19}

看完带走：最终根代表整个连通分量，直接父节点只代表森林中的一条链接。

06交互算法精讲

如何构建 find、判环、union 的固定顺序

对每条边先求 rootU、rootV。若相同，旧图已经存在一条 u 到 v 的路径，当前边与旧路径组成环，立即返回；若不同，当前边连接两个分量，不可能成环。

合并时修改根节点的 parent，例如 `parent[rootV]=rootU`。若直接写 `parent[v]=u`，可能只移动一个普通节点而没有正确合并整个集合。

• find 负责回答所属连通分量。
• 同根判断负责识别闭环边。
• union 只接纳已证明安全的异根边。

创建长度 len(edges)+1 的 parent，覆盖编号 1..n。find 递归寻找根，并在返回时执行路径压缩。

遍历每条边：若两个根相同直接返回 edge；否则令其中一个根指向另一个根。题目保证存在答案。

先写 `parent[rootU]=rootV`，而不是 `parent[u]=v`；只有根节点代表整个集合，合并普通节点可能破坏集合结构。

动画 4 · 机制构建

严格按 find、判断、union 的顺序处理边

逐边观察异根时接纳并合并，同根时停止并返回，确认判断发生在 union 之前。

Step 1/50%

检查 [1,2]

root 1

root 2

root 3

find(1)=1 != find(2)=2

边 [1,2] 两端根不同

发生了什么: find(1)=1，find(2)=2，旧图中 1 与 2 尚未连通。
为什么: 根不同表示属于不同连通分量，加入这条边不会形成环。
下一步: 接纳边 [1,2] 并合并两个根。

当前状态

rootU / rootV

1 / 2

当前 Go 代码

1func findRedundantConnection(edges [][]int) []int {2    parent := make([]int, len(edges)+1)3    for i := range parent { parent[i] = i }4    var find func(int) int5    find = func(x int) int {6        if parent[x] != x {7            parent[x] = find(parent[x])8        }9        return parent[x]10    }11    for _, edge := range edges {12        rootU, rootV := find(edge[0]), find(edge[1])13        if rootU == rootV {14            return edge15        }16        parent[rootV] = rootU17    }18    return nil19}

看完带走：异根边连接分量，同根边闭合旧路径；两种情况绝不能交换处理顺序。

07交互算法精讲

核心难点：为什么同根边必然闭合环

在处理当前边 [u,v] 前，并查集只包含已经接纳的旧边。find(u)==find(v) 表示旧图中存在一条由这些边组成的 u 到 v 路径。

无向图中再加入直接边 u—v，会让 u、v 之间同时存在旧路径和新边两条不同路线，两者合起来必然形成一个环。因此当前边可以删除而不破坏旧图连通性。

根不同则旧图中不存在 u 到 v 的路径，新边只是把两个分量连接起来，不可能闭环。按输入顺序第一次出现同根，正是环上最后被加入、让环真正形成的边。

题目保证原结构是树加一条边，所以只会出现一个环；顺序扫描的第一次同根边就是满足靠后规则的答案。

正确性抓手

• 不同根表示旧图中两端不连通，加入边不会形成环，union 正确合并分量。
• 相同根表示旧图已有一条 u 到 v 的路径，新边必然闭合且只会闭合一个环。
• 按输入顺序返回第一次同根边，等价于返回该环中最后被处理的候选边。

08交互算法精讲

完整执行过程

按输入顺序处理三条边。观察前两条边如何合并集合，以及第三条边的两个端点为何在加入前已经拥有同一个根。

1初始化 parent[1]=1、parent[2]=2、parent[3]=3，三个节点互不连通。
2处理 [1,2]：find 得到 1 和 2，根不同，接纳边并令 parent[2]=1。
3处理 [1,3]：根仍不同，接纳边并令 parent[3]=1；此时三个节点已经连通。
4处理 [2,3]：find(2)=1、find(3)=1，旧图已有路径 2—1—3。
5新边 [2,3] 与旧路径闭合三角环，立即返回 [2,3]，不再执行 union。

动画 5 · 完整执行

三条边完整执行到 [2,3] 闭环

从初始化播放到输入顺序结论，观察 parent、根、已接纳边和冗余边同步变化。

Step 1/90%

输入边按顺序处理

root 1

root 2

root 3

[1,2] → [1,3] → [2,3]

原树多出一条边后出现环

发生了什么: 输入依次是 [1,2]、[1,3]、[2,3]，最终三条边围成一个环。
为什么: 树已有 n-1 条边且连通，再加一条边会在唯一旧路径上闭合环。
下一步: 先让每个节点成为自己的集合根。

当前状态

nodes / edges

3 / 3

当前 Go 代码

1func findRedundantConnection(edges [][]int) []int {2    parent := make([]int, len(edges)+1)3    for i := range parent { parent[i] = i }4    var find func(int) int5    find = func(x int) int {6        if parent[x] != x {7            parent[x] = find(parent[x])8        }9        return parent[x]10    }11    for _, edge := range edges {12        rootU, rootV := find(edge[0]), find(edge[1])13        if rootU == rootV {14            return edge15        }16        parent[rootV] = rootU17    }18    return nil19}

看完带走：前两条边构成旧路径，第三条同根边才让环真正闭合。

09交互算法精讲

把动画和 Go 代码逐行对应

每一帧使用稳定的语义行 ID，不依赖容易漂移的数字行号。先观察分支为什么成立，再看对应代码，而不是先背模板。

动画 6 · 代码映射

find、同根返回与 union 逐行对应

观察路径压缩后的根值、同根条件和返回分支，尤其避免直接比较 parent。

Step 1/50%

并查集初始化

root 1

root 2

root 3

parent

1→12→23→3

parent=[0,1,2,3]

每个节点一开始都是独立集合

发生了什么: 初始化 parent[1]=1、parent[2]=2、parent[3]=3。
为什么: 还没有处理任何边，节点之间尚未建立连通关系。
下一步: 对第一条边 [1,2] 的两端执行 find。

当前状态

components

当前 Go 代码

1func findRedundantConnection(edges [][]int) []int {2    parent := make([]int, len(edges)+1)3    for i := range parent { parent[i] = i }4    var find func(int) int5    find = func(x int) int {6        if parent[x] != x {7            parent[x] = find(parent[x])8        }9        return parent[x]10    }11    for _, edge := range edges {12        rootU, rootV := find(edge[0]), find(edge[1])13        if rootU == rootV {14            return edge15        }16        parent[rootV] = rootU17    }18    return nil19}

看完带走：代码必须先保存两个最终根，再决定 return 或合并两个根。

Step 1

原树多出一条边后出现环

树已有 n-1 条边且连通，再加一条边会在唯一旧路径上闭合环。

func · parent-init

Step 2

每个节点一开始都是独立集合

还没有处理任何边，节点之间尚未建立连通关系。

parent-init · init-loop

Step 3

边 [1,2] 两端根不同

根不同表示属于不同连通分量，加入这条边不会形成环。

edge-loop · find-roots · same-root-check

Step 4

接纳 [1,2]，两个集合合并

合并根节点后，find(1) 与 find(2) 都会得到代表根 1。

union

Step 5

边 [1,3] 也安全，三个节点连成一棵树

加入第二条边时，旧图中还没有 1 到 3 的路径。

find-roots · same-root-check · union

Step 6

处理 [2,3]：两端已经同根

前两条边已经提供路径 2→1→3，两个端点属于同一连通分量。

find-call · path-compress · find-roots · same-root-check

Step 7

同根端点再连接，当前边闭合环

同根证明旧图已经存在 u 到 v 的路径；新边增加第二条路线，环因此形成。

same-root-check · return-edge

Step 8

按序第一次同根，正是环中最后出现的边

因此顺序扫描并返回第一次同根边，满足题目要求的靠后候选。

edge-loop · same-root-check · return-edge

Step 9

路径压缩让 find 接近常数

并查集的摊还复杂度是反阿克曼函数 α(n)，实际规模下增长极慢。

find-call · path-compress · edge-loop · return-edge

10交互算法精讲

完整 Go 提交代码与最小测试

完整 Go 解法

1func findRedundantConnection(edges [][]int) []int {2    parent := make([]int, len(edges)+1)3    for i := range parent { parent[i] = i }4    var find func(int) int5    find = func(x int) int {6        if parent[x] != x {7            parent[x] = find(parent[x])8        }9        return parent[x]10    }11    for _, edge := range edges {12        rootU, rootV := find(edge[0]), find(edge[1])13        if rootU == rootV {14            return edge15        }16        parent[rootV] = rootU17    }18    return nil19}

最小测试集合

// 三角环，最后一条边冗余
findRedundantConnection([][]int{{1,2},{1,3},{2,3}}) // [2,3]

// 四节点环
findRedundantConnection([][]int{{1,2},{2,3},{3,4},{1,4},{1,5}}) // [1,4]

// 长链最后闭合到起点
findRedundantConnection([][]int{{1,2},{2,3},{3,4},{4,1}}) // [4,1]

// 节点编号从 1 开始，parent 必须有 n+1 个位置
findRedundantConnection([][]int{{1,2},{2,3},{3,1}}) // [3,1]

11交互算法精讲

正确性与复杂度

时间复杂度 O(n α(n))

n 条边各执行常数次 find/union；路径压缩后单次操作的摊还成本为 α(n)，实际接近常数。

空间复杂度 O(n)

parent 数组保存每个节点的并查集父指针，递归 find 的栈也受树高约束。

12交互算法精讲

最容易写错的地方

错误 1

直接比较 parent[u] 与 parent[v]，没有找到最终根。

错误 2

先 union 再判断同根，错过当前冗余边。

错误 3

合并普通节点 parent[u]=v，而不是合并两个根。

错误 4

parent 长度没有覆盖从 1 开始的节点编号。

13交互算法精讲

最后复盘：带走逻辑链

1.并查集把“旧图是否已有路径”压缩成同根判断。
2.异根边安全，接纳并合并；同根边闭环，立即返回。
3.路径压缩优化 find，不改变集合语义。
4.迁移题：LC547 省份数量、LC261 图是否为树。

面试表达

1.这题是无向图判环，用并查集维护已经处理边形成的连通关系。
2.每条边先 find 两端；根不同就 union，根相同说明旧图已有路径，当前边闭合环。
3.按输入顺序扫描并立即返回同根边，符合题目要求的靠后候选。
4.路径压缩后时间 O(n α(n))，parent 空间 O(n)。