无向图
边没有方向，1-2 等于 2-1。
这题的边 [u,v] 只表示 u 和 v 连上，不表示 u 指向 v。
LC684
LC684 冗余连接：找出让树变成环的那条边
一棵树本来没有环。现在多加了一条边，图里出现了一个环。我们要找出哪条边是多余的，删掉它之后图又能恢复成树。
时间复杂度：O(n α(n))，面试中可近似为 O(n)空间复杂度：O(n)，因为需要 parent 数组
module 1
题目在问什么
给你一个无向图，它原本是一棵树。
后来多加了一条边，所以出现了一个环。
返回那条可以删掉的边。
什么是冗余边？删掉它之后，剩下的图仍然连通，而且不再有环。
example
edges = [[1,2], [1,3], [2,3]]
答案：[2,3]
module 2
先补概念
树
连通且无环的图。
任意两点之间原本只有一条简单路径。
连通
两个点之间有路能走到。
不一定直接相邻，中间可以经过别的点。
环
从一个点出发，绕一圈还能回到自己。
旧路径加上一条新边，就把圈闭合了。
冗余边
删掉后仍然能保持连通的多余边。
它不是唯一能删的边时，题目要返回输入顺序里让环闭合的那条。
并查集
快速判断两个点是否已经在同一组。
适合反复问“之前是否连通”。
parent
每个节点当前指向的集合代表。
parent 数组是并查集的内部账本，不是图上所有边。
root
一个集合最终的老大。
find(x) 一路沿 parent 找到 root。
module 3
为什么用并查集
这题的核心问题不是求最短路，也不是遍历所有路径，而是反复判断：
两个点之前是否已经连通？
如果没连通，就把它们合并。
如果已经连通，再加这条边就会形成环。
这正是并查集擅长的事情。
find(u) == find(v) 不是神奇判断，它表示 u 和 v 之前已经在同一个连通块里。
如果两个点本来已经有一条旧路径，现在又加一条新边，就会形成环。
并查集不是用来画图的，它是用来快速回答：两个点是不是已经连通？
这题的关键不是找所有环，而是找到第一条让环闭合的边。
module 4
交互动画实验台
切换示例
帧 1/5
左侧：输入边队列
edges = [[1,2], [1,3], [2,3]]
[1,2]等待
[1,3]等待
[2,3]等待
find 路径
当前还没有执行 find。
动态图画布
蓝色：已经安全连接
黄色：当前处理的边
红色：形成环的边
右侧：parent 表
| node | parent[node] |
|---|---|
| 1 | 待初始化 |
| 2 | 待初始化 |
| 3 | 待初始化 |
我们会按顺序处理每一条边。
还没有执行 union。
我们会按顺序处理每一条边。
module 5
代码讲解
1func findRedundantConnection(edges [][]int) []int {2 n := len(edges)3 parent := make([]int, n+1)45 for i := 1; i <= n; i++ {6 parent[i] = i7 }89 var find func(int) int10 find = func(x int) int {11 if parent[x] != x {12 parent[x] = find(parent[x])13 }14 return parent[x]15 }1617 union := func(a, b int) bool {18 rootA := find(a)19 rootB := find(b)2021 if rootA == rootB {22 return false23 }2425 parent[rootB] = rootA26 return true27 }2829 for _, edge := range edges {30 a, b := edge[0], edge[1]31 if !union(a, b) {32 return edge33 }34 }3536 return nil37}lines 2-7
parent 初始化
先给每个点分配一个集合：1 指向 1，2 指向 2，表示大家一开始互不连通。
lines 9-15
find(x)
找到 x 所属集合的最终代表，也就是 root。
lines 11-12
路径压缩
parent[x] = find(parent[x]) 会把沿途节点直接挂到 root 下，让后续查询更快。
lines 17-27
union(a,b)
先比较 rootA 和 rootB。rootA == rootB 说明两个点已经连通，不能再连。
lines 29-34
return edge
遍历 edges 时第一次 union 失败，当前边就是让环闭合的边。
rootA == rootB：说明两个点已经连通。return edge：当前边就是让环闭合的边。
module 6
面试怎么说
这题是无向图找环。题目保证图原本是一棵树，只是多加了一条边，所以一定只会出现一个环。
我按输入顺序遍历每条边，用并查集维护当前已经连通的节点集合。
对于边 [u, v]：
如果 find(u) != find(v)，说明 u 和 v 之前不连通，可以 union。
如果 find(u) == find(v)，说明 u 和 v 之前已经有路径连通，再加这条边就会形成环，所以当前边就是冗余边。
时间复杂度 O(n α(n))，空间复杂度 O(n)。
什么是冗余边？删掉后仍然保持连通、并且能去掉环的那条多余边。
为什么 find(u) == find(v) 会成环？因为 u 和 v 之前已有旧路径，新边会把旧路径闭合。
为什么适合并查集？因为它快速回答两个点是不是已经连通。