【华为机试】684. 冗余连接_华为机试题解

技术文档

文章目录

684. 冗余连接
- 描述
- 示例 1
- 示例 2
- 提示
- 解题思路
- - 核心分析
  - 问题转化
  - 算法选择策略
  - - 1. 并查集 (Union-Find) - 推荐
    - 2. 深度优先搜索 (DFS)
    - 3. 拓扑排序
  - 算法实现详解
  - - 方法一：并查集 (Union-Find)
    - 方法二：深度优先搜索 (DFS)
  - 数学证明
  - - 并查集算法正确性证明
    - 时间复杂度分析
  - 执行流程图
  - 算法可视化
  - 实际应用
  - 算法优化技巧
  - - 1. 路径压缩优化
    - 2. 按秩合并优化
    - 3. 早期终止
  - 扩展思考
  - 相关问题
  - 测试用例设计
  - 性能对比
  - 常见错误
  - 总结
- 完整题解代码

684. 冗余连接

描述

树可以看成是一个连通且无环的无向图。

给定一个图，该图从一棵 n 个节点 (节点值 1～n) 的树中添加一条边后获得。添加的边的两个不同顶点编号在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

示例 1

在这里插入图片描述

输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]

示例 2

在这里插入图片描述

输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]

提示

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges 中无重复元素
给定的图是连通的

解题思路

核心分析

这道题是一个经典的并查集应用问题。核心思想是找到导致图中出现环的那条边。

问题本质：给定一个包含n条边的连通图，其中n-1条边构成一棵树，1条边是冗余的，需要找到这条冗余边。

关键洞察：

树的性质：n个节点的树有n-1条边，无环且连通
冗余边的特征：添加这条边后会在图中形成环
并查集的作用：维护连通性，检测环的形成

问题转化

原始问题：找到一条边，删除后剩余图是一棵树

并查集转化：

初始化并查集，每个节点自成一个集合
按顺序处理每条边
如果边的两个端点已经在同一集合中，说明这条边会形成环
这条边就是需要删除的冗余边

数学建模：

节点集合：V = {1, 2, 3, …, n}
边集合：E = {e1, e2, e3, …, en}
目标：找到边ei，使得E - {ei}构成一棵树

算法选择策略

1. 并查集 (Union-Find) - 推荐

适用场景：动态连通性问题，需要检测环的形成
优势：时间复杂度最优，实现相对简单
劣势：需要理解并查集的工作原理

2. 深度优先搜索 (DFS)

适用场景：需要检测环的存在
优势：思路直观，容易理解
劣势：时间复杂度较高，实现复杂

3. 拓扑排序

适用场景：有向图的环检测
优势：可以找到所有环
劣势：本题是无向图，不适用

算法实现详解

方法一：并查集 (Union-Find)

核心思想：使用并查集维护连通性，当遇到会形成环的边时，该边就是冗余边

算法步骤：

初始化并查集，每个节点自成一个集合
按顺序遍历每条边
对于每条边[u, v]：
- 查找u和v的根节点
- 如果根节点相同，说明u和v已经连通，这条边会形成环
- 如果根节点不同，合并两个集合
返回最后一条会形成环的边

代码实现：

func findRedundantConnection(edges [][]int) []int { n := len(edges) uf := NewUnionFind(n + 1) // 节点编号从1开始 for _, edge := range edges { u, v := edge[0], edge[1] if uf.Find(u) == uf.Find(v) { // 这条边会形成环，返回这条边 return edge } uf.Union(u, v) } return nil}type UnionFind struct { parent []int rank []int}func NewUnionFind(n int) *UnionFind { parent := make([]int, n) rank := make([]int, n) for i := 0; i < n; i++ { parent[i] = i rank[i] = 1 } return &UnionFind{ parent: parent, rank: rank, }}func (uf *UnionFind) Find(x int) int { if uf.parent[x] != x { uf.parent[x] = uf.Find(uf.parent[x]) // 路径压缩 } return uf.parent[x]}func (uf *UnionFind) Union(x, y int) { rootX := uf.Find(x) rootY := uf.Find(y) if rootX == rootY { return } // 按秩合并 if uf.rank[rootX] < uf.rank[rootY] { uf.parent[rootX] = rootY } else if uf.rank[rootX] > uf.rank[rootY] { uf.parent[rootY] = rootX } else { uf.parent[rootY] = rootX uf.rank[rootX]++ }}

时间复杂度分析：

每条边最多处理一次：O(n)
每次Find/Union操作：O(α(n))
总时间复杂度：O(n × α(n))

空间复杂度分析：

并查集数组：O(n)
总空间复杂度：O(n)

方法二：深度优先搜索 (DFS)

核心思想：对每条边，检查删除该边后图中是否还有环

算法步骤：

构建邻接表表示图
从最后一条边开始，依次尝试删除每条边
对于每条被删除的边，使用DFS检查剩余图是否还有环
如果删除某条边后图中无环，则该边是冗余边

代码实现：

func findRedundantConnectionDFS(edges [][]int) []int { n := len(edges) // 从最后一条边开始尝试删除 for i := n - 1; i >= 0; i-- { // 构建删除边i后的图 graph := make(map[int][]int) for j := 0; j < n; j++ { if j != i { u, v := edges[j][0], edges[j][1] graph[u] = append(graph[u], v) graph[v] = append(graph[v], u) } } // 检查是否有环 if !hasCycle(graph, n) { return edges[i] } } return nil}func hasCycle(graph map[int][]int, n int) bool { visited := make([]bool, n+1) for i := 1; i <= n; i++ { if !visited[i] { if dfsHasCycle(graph, visited, i, -1) { return true } } } return false}func dfsHasCycle(graph map[int][]int, visited []bool, node, parent int) bool { visited[node] = true for _, neighbor := range graph[node] { if !visited[neighbor] { if dfsHasCycle(graph, visited, neighbor, node) { return true } } else if neighbor != parent { // 访问到已访问的节点且不是父节点，说明有环 return true } } return false}

时间复杂度：O(n²)
空间复杂度：O(n)

数学证明

并查集算法正确性证明

定理：并查集算法能正确找到冗余边。

证明：

初始化正确性：
- 初始时每个节点自成一个集合
- 图中没有边，没有环
处理过程正确性：
- 每次处理边[u, v]时，如果u和v已在同一集合中，说明u和v已经连通
- 添加边[u, v]会在u和v之间形成环
- 因此边[u, v]是冗余边
结果正确性：
- 删除冗余边后，剩余n-1条边
- 由于原图连通，删除一条边后仍然连通
- 没有环，因此剩余图是一棵树

时间复杂度分析

定理：并查集算法的时间复杂度为O(n × α(n))。

证明：

每条边最多处理一次：O(n)
每次Find/Union操作的时间复杂度：O(α(n))
总时间复杂度：O(n × α(n))

执行流程图

#mermaid-svg-QtWy5hpGD9uWK7iw {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-QtWy5hpGD9uWK7iw .error-icon{fill:#552222;}#mermaid-svg-QtWy5hpGD9uWK7iw .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-QtWy5hpGD9uWK7iw .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-QtWy5hpGD9uWK7iw .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-QtWy5hpGD9uWK7iw .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-QtWy5hpGD9uWK7iw .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-QtWy5hpGD9uWK7iw .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-QtWy5hpGD9uWK7iw .marker{fill:#333333;stroke:#333333;}#mermaid-svg-QtWy5hpGD9uWK7iw .marker.cross{stroke:#333333;}#mermaid-svg-QtWy5hpGD9uWK7iw svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-QtWy5hpGD9uWK7iw .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-QtWy5hpGD9uWK7iw .cluster-label text{fill:#333;}#mermaid-svg-QtWy5hpGD9uWK7iw .cluster-label span{color:#333;}#mermaid-svg-QtWy5hpGD9uWK7iw .label text,#mermaid-svg-QtWy5hpGD9uWK7iw span{fill:#333;color:#333;}#mermaid-svg-QtWy5hpGD9uWK7iw .node rect,#mermaid-svg-QtWy5hpGD9uWK7iw .node circle,#mermaid-svg-QtWy5hpGD9uWK7iw .node ellipse,#mermaid-svg-QtWy5hpGD9uWK7iw .node polygon,#mermaid-svg-QtWy5hpGD9uWK7iw .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-QtWy5hpGD9uWK7iw .node .label{text-align:center;}#mermaid-svg-QtWy5hpGD9uWK7iw .node.clickable{cursor:pointer;}#mermaid-svg-QtWy5hpGD9uWK7iw .arrowheadPath{fill:#333333;}#mermaid-svg-QtWy5hpGD9uWK7iw .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-QtWy5hpGD9uWK7iw .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-QtWy5hpGD9uWK7iw .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-QtWy5hpGD9uWK7iw .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-QtWy5hpGD9uWK7iw .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-QtWy5hpGD9uWK7iw .cluster text{fill:#333;}#mermaid-svg-QtWy5hpGD9uWK7iw .cluster span{color:#333;}#mermaid-svg-QtWy5hpGD9uWK7iw div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-QtWy5hpGD9uWK7iw :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 是否否是开始: 输入边数组edges 初始化并查集遍历每条边 i = 0 to n-1 获取当前边的两个端点 u, v 查找u和v的根节点根节点是否相同? 这条边会形成环返回这条边作为冗余边结束合并u和v所在的集合继续处理下一条边是否处理完所有边? 返回nil

算法可视化

#mermaid-svg-zgP0PrEKW0ewWrdk {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-zgP0PrEKW0ewWrdk .error-icon{fill:#552222;}#mermaid-svg-zgP0PrEKW0ewWrdk .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-zgP0PrEKW0ewWrdk .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-zgP0PrEKW0ewWrdk .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-zgP0PrEKW0ewWrdk .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-zgP0PrEKW0ewWrdk .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-zgP0PrEKW0ewWrdk .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-zgP0PrEKW0ewWrdk .marker{fill:#333333;stroke:#333333;}#mermaid-svg-zgP0PrEKW0ewWrdk .marker.cross{stroke:#333333;}#mermaid-svg-zgP0PrEKW0ewWrdk svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-zgP0PrEKW0ewWrdk .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-zgP0PrEKW0ewWrdk .cluster-label text{fill:#333;}#mermaid-svg-zgP0PrEKW0ewWrdk .cluster-label span{color:#333;}#mermaid-svg-zgP0PrEKW0ewWrdk .label text,#mermaid-svg-zgP0PrEKW0ewWrdk span{fill:#333;color:#333;}#mermaid-svg-zgP0PrEKW0ewWrdk .node rect,#mermaid-svg-zgP0PrEKW0ewWrdk .node circle,#mermaid-svg-zgP0PrEKW0ewWrdk .node ellipse,#mermaid-svg-zgP0PrEKW0ewWrdk .node polygon,#mermaid-svg-zgP0PrEKW0ewWrdk .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-zgP0PrEKW0ewWrdk .node .label{text-align:center;}#mermaid-svg-zgP0PrEKW0ewWrdk .node.clickable{cursor:pointer;}#mermaid-svg-zgP0PrEKW0ewWrdk .arrowheadPath{fill:#333333;}#mermaid-svg-zgP0PrEKW0ewWrdk .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-zgP0PrEKW0ewWrdk .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-zgP0PrEKW0ewWrdk .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-zgP0PrEKW0ewWrdk .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-zgP0PrEKW0ewWrdk .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-zgP0PrEKW0ewWrdk .cluster text{fill:#333;}#mermaid-svg-zgP0PrEKW0ewWrdk .cluster span{color:#333;}#mermaid-svg-zgP0PrEKW0ewWrdk div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-zgP0PrEKW0ewWrdk :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 并查集状态变化示例1: edges = [[1,2], [1,3], [2,3]] 初始: {1}, {2}, {3} 边[1,2]: {1,2}, {3} 边[1,3]: {1,2,3} 边[2,3]: 1和2已在同一集合处理边[1,2] 处理边[1,3] 处理边[2,3] - 发现环

实际应用

网络拓扑设计：检测网络中的冗余连接
电路设计：识别电路中的冗余线路
社交网络分析：发现社交网络中的冗余关系
数据库设计：检测数据库中的冗余约束
软件架构：识别模块间的冗余依赖

算法优化技巧

1. 路径压缩优化

func (uf *UnionFind) Find(x int) int { if uf.parent[x] != x { uf.parent[x] = uf.Find(uf.parent[x]) // 路径压缩 } return uf.parent[x]}

2. 按秩合并优化

func (uf *UnionFind) Union(x, y int) { rootX := uf.Find(x) rootY := uf.Find(y) if rootX == rootY { return } // 按秩合并，保持树的平衡 if uf.rank[rootX] < uf.rank[rootY] { uf.parent[rootX] = rootY } else if uf.rank[rootX] > uf.rank[rootY] { uf.parent[rootY] = rootX } else { uf.parent[rootY] = rootX uf.rank[rootX]++ }}

3. 早期终止

// 如果已经找到冗余边，可以提前终止for _, edge := range edges { u, v := edge[0], edge[1] if uf.Find(u) == uf.Find(v) { return edge // 找到冗余边，立即返回 } uf.Union(u, v)}

扩展思考

多条冗余边：如果有多条冗余边，如何找到所有冗余边？
加权图：如果边有权重，如何找到权重最小的冗余边？
有向图：如果是有向图，如何检测环？
动态图：如果图结构动态变化，如何维护冗余边的信息？
最小生成树：如何利用冗余边检测构建最小生成树？

测试用例设计

// 基础测试用例edges1 := [][]int{{1, 2}, {1, 3}, {2, 3}}expected1 := []int{2, 3}edges2 := [][]int{{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}}expected2 := []int{1, 4}// 边界测试edges3 := [][]int{{1, 2}, {2, 3}, {3, 1}}expected3 := []int{3, 1}// 复杂情况edges4 := [][]int{{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 1}}expected4 := []int{6, 1}// 多条冗余边的情况edges5 := [][]int{{1, 2}, {2, 3}, {3, 4}, {4, 1}, {1, 3}}expected5 := []int{1, 3} // 返回最后出现的冗余边

性能对比

算法时间复杂度空间复杂度优势劣势并查集 O(n × α(n)) O(n) 最优解，实现简单需要理解并查集 DFS O(n²) O(n) 思路直观时间复杂度高 BFS O(n²) O(n) 避免递归实现复杂

常见错误

并查集初始化错误：忘记初始化parent数组
节点编号错误：节点编号从1开始，但数组索引从0开始
环检测错误：没有正确检测环的形成
返回顺序错误：没有按照题目要求返回最后出现的冗余边
边界处理错误：没有处理空数组或单个节点的情况

总结

冗余连接 是一道经典的并查集应用问题，核心在于理解环的形成机制和并查集的维护策略。

最优解法是并查集算法，具有以下优势：

时间复杂度最优：O(n × α(n))
实现简单：核心逻辑只有几行
空间效率高：只需要O(n)额外空间
应用广泛：是并查集的经典模板题

这道题体现了图论算法中的重要思想：

环检测：通过并查集检测环的形成
动态连通性：维护图的连通性信息
问题建模：将环检测问题转化为并查集操作

关键技巧：

使用路径压缩和按秩合并优化并查集性能
按顺序处理边，找到第一条会形成环的边
理解树的性质：n个节点的树有n-1条边，无环且连通

完整题解代码

package mainimport (\"fmt\")// 方法一：并查集 (Union-Find) - 推荐解法// 时间复杂度：O(n × α(n))，空间复杂度：O(n)func findRedundantConnection(edges [][]int) []int {n := len(edges)uf := NewUnionFind(n + 1) // 节点编号从1开始for _, edge := range edges {u, v := edge[0], edge[1]if uf.Find(u) == uf.Find(v) {// 这条边会形成环，返回这条边return edge}uf.Union(u, v)}return nil}// 并查集结构type UnionFind struct {parent []intrank []int}// 创建新的并查集func NewUnionFind(n int) *UnionFind {parent := make([]int, n)rank := make([]int, n)for i := 0; i < n; i++ {parent[i] = irank[i] = 1}return &UnionFind{parent: parent,rank: rank,}}// 查找根节点（路径压缩）func (uf *UnionFind) Find(x int) int {if uf.parent[x] != x {uf.parent[x] = uf.Find(uf.parent[x]) // 路径压缩}return uf.parent[x]}// 合并两个集合（按秩合并）func (uf *UnionFind) Union(x, y int) {rootX := uf.Find(x)rootY := uf.Find(y)if rootX == rootY {return}// 按秩合并if uf.rank[rootX] < uf.rank[rootY] {uf.parent[rootX] = rootY} else if uf.rank[rootX] > uf.rank[rootY] {uf.parent[rootY] = rootX} else {uf.parent[rootY] = rootXuf.rank[rootX]++}}// 方法二：深度优先搜索 (DFS)// 时间复杂度：O(n²)，空间复杂度：O(n)func findRedundantConnectionDFS(edges [][]int) []int {n := len(edges)// 从最后一条边开始尝试删除for i := n - 1; i >= 0; i-- {// 构建删除边i后的图graph := make(map[int][]int)for j := 0; j < n; j++ {if j != i {u, v := edges[j][0], edges[j][1]graph[u] = append(graph[u], v)graph[v] = append(graph[v], u)}}// 检查是否有环if !hasCycle(graph, n) {return edges[i]}}return nil}// 检查图中是否有环func hasCycle(graph map[int][]int, n int) bool {visited := make([]bool, n+1)for i := 1; i <= n; i++ {if !visited[i] {if dfsHasCycle(graph, visited, i, -1) {return true}}}return false}// DFS检测环func dfsHasCycle(graph map[int][]int, visited []bool, node, parent int) bool {visited[node] = truefor _, neighbor := range graph[node] {if !visited[neighbor] {if dfsHasCycle(graph, visited, neighbor, node) {return true}} else if neighbor != parent {// 访问到已访问的节点且不是父节点，说明有环return true}}return false}// 方法三：优化的并查集（简化版）// 时间复杂度：O(n × α(n))，空间复杂度：O(n)func findRedundantConnectionOptimized(edges [][]int) []int {n := len(edges)parent := make([]int, n+1)// 初始化并查集for i := 1; i <= n; i++ {parent[i] = i}// 查找函数（带路径压缩）var find func(x int) intfind = func(x int) int {if parent[x] != x {parent[x] = find(parent[x])}return parent[x]}// 合并函数union := func(x, y int) bool {rootX := find(x)rootY := find(y)if rootX == rootY {return false // 已经在同一集合中}parent[rootX] = rootYreturn true}for _, edge := range edges {u, v := edge[0], edge[1]if !union(u, v) {// 无法合并，说明会形成环return edge}}return nil}// 方法四：广度优先搜索 (BFS)// 时间复杂度：O(n²)，空间复杂度：O(n)func findRedundantConnectionBFS(edges [][]int) []int {n := len(edges)// 从最后一条边开始尝试删除for i := n - 1; i >= 0; i-- {// 构建删除边i后的图graph := make(map[int][]int)for j := 0; j < n; j++ {if j != i {u, v := edges[j][0], edges[j][1]graph[u] = append(graph[u], v)graph[v] = append(graph[v], u)}}// 检查是否有环if !hasCycleBFS(graph, n) {return edges[i]}}return nil}// BFS检测环func hasCycleBFS(graph map[int][]int, n int) bool {visited := make([]bool, n+1)for i := 1; i <= n; i++ {if !visited[i] {if bfsHasCycle(graph, visited, i) {return true}}}return false}// BFS检测环的具体实现func bfsHasCycle(graph map[int][]int, visited []bool, start int) bool {queue := [][]int{{start, -1}} // [节点, 父节点]visited[start] = truefor len(queue) > 0 {node, parent := queue[0][0], queue[0][1]queue = queue[1:]for _, neighbor := range graph[node] {if !visited[neighbor] {visited[neighbor] = truequeue = append(queue, []int{neighbor, node})} else if neighbor != parent {// 访问到已访问的节点且不是父节点，说明有环return true}}}return false}// 测试函数func main() {// 测试用例1：示例1edges1 := [][]int{{1, 2}, {1, 3}, {2, 3}}fmt.Println(\"测试用例1:\")fmt.Printf(\"输入: %v\\n\", edges1)fmt.Printf(\"并查集结果: %v\\n\", findRedundantConnection(edges1))fmt.Printf(\"DFS结果: %v\\n\", findRedundantConnectionDFS(edges1))fmt.Printf(\"优化并查集结果: %v\\n\", findRedundantConnectionOptimized(edges1))fmt.Printf(\"BFS结果: %v\\n\", findRedundantConnectionBFS(edges1))fmt.Println(\"期望结果: [2 3]\")fmt.Println()// 测试用例2：示例2edges2 := [][]int{{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}}fmt.Println(\"测试用例2:\")fmt.Printf(\"输入: %v\\n\", edges2)fmt.Printf(\"并查集结果: %v\\n\", findRedundantConnection(edges2))fmt.Printf(\"DFS结果: %v\\n\", findRedundantConnectionDFS(edges2))fmt.Printf(\"优化并查集结果: %v\\n\", findRedundantConnectionOptimized(edges2))fmt.Printf(\"BFS结果: %v\\n\", findRedundantConnectionBFS(edges2))fmt.Println(\"期望结果: [1 4]\")fmt.Println()// 测试用例3：边界情况 - 三角形环edges3 := [][]int{{1, 2}, {2, 3}, {3, 1}}fmt.Println(\"测试用例3 (三角形环):\")fmt.Printf(\"输入: %v\\n\", edges3)fmt.Printf(\"并查集结果: %v\\n\", findRedundantConnection(edges3))fmt.Printf(\"DFS结果: %v\\n\", findRedundantConnectionDFS(edges3))fmt.Printf(\"优化并查集结果: %v\\n\", findRedundantConnectionOptimized(edges3))fmt.Printf(\"BFS结果: %v\\n\", findRedundantConnectionBFS(edges3))fmt.Println(\"期望结果: [3 1]\")fmt.Println()// 测试用例4：复杂情况 - 大环edges4 := [][]int{{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 1}}fmt.Println(\"测试用例4 (大环):\")fmt.Printf(\"输入: %v\\n\", edges4)fmt.Printf(\"并查集结果: %v\\n\", findRedundantConnection(edges4))fmt.Printf(\"DFS结果: %v\\n\", findRedundantConnectionDFS(edges4))fmt.Printf(\"优化并查集结果: %v\\n\", findRedundantConnectionOptimized(edges4))fmt.Printf(\"BFS结果: %v\\n\", findRedundantConnectionBFS(edges4))fmt.Println(\"期望结果: [6 1]\")fmt.Println()// 测试用例5：多条冗余边的情况edges5 := [][]int{{1, 2}, {2, 3}, {3, 4}, {4, 1}, {1, 3}}fmt.Println(\"测试用例5 (多条冗余边):\")fmt.Printf(\"输入: %v\\n\", edges5)fmt.Printf(\"并查集结果: %v\\n\", findRedundantConnection(edges5))fmt.Printf(\"DFS结果: %v\\n\", findRedundantConnectionDFS(edges5))fmt.Printf(\"优化并查集结果: %v\\n\", findRedundantConnectionOptimized(edges5))fmt.Printf(\"BFS结果: %v\\n\", findRedundantConnectionBFS(edges5))fmt.Println(\"期望结果: [1 3] (返回最后出现的冗余边)\")fmt.Println()// 测试用例6：最小情况edges6 := [][]int{{1, 2}, {2, 3}, {3, 1}}fmt.Println(\"测试用例6 (最小情况):\")fmt.Printf(\"输入: %v\\n\", edges6)fmt.Printf(\"并查集结果: %v\\n\", findRedundantConnection(edges6))fmt.Printf(\"DFS结果: %v\\n\", findRedundantConnectionDFS(edges6))fmt.Printf(\"优化并查集结果: %v\\n\", findRedundantConnectionOptimized(edges6))fmt.Printf(\"BFS结果: %v\\n\", findRedundantConnectionBFS(edges6))fmt.Println(\"期望结果: [3 1]\")}