做微信电影网站,广东网站建设商家,net源码的网站建设步骤,承接网络推广外包业务文章目录684. 冗余连接描述示例 1示例 2提示解题思路核心分析问题转化算法选择策略1. 并查集 (Union-Find) - 推荐2. 深度优先搜索 (DFS)3. 拓扑排序算法实现详解方法一#xff1a;并查集 (Union-Find)方法二#xff1a;深度优先搜索 (DFS)数学证明并查集算法正确性证明时间复…
文章目录684. 冗余连接描述示例 1示例 2提示解题思路核心分析问题转化算法选择策略1. 并查集 (Union-Find) - 推荐2. 深度优先搜索 (DFS)3. 拓扑排序算法实现详解方法一并查集 (Union-Find)方法二深度优先搜索 (DFS)数学证明并查集算法正确性证明时间复杂度分析执行流程图算法可视化实际应用算法优化技巧1. 路径压缩优化2. 按秩合并优化3. 早期终止扩展思考相关问题测试用例设计性能对比常见错误总结完整题解代码684. 冗余连接
描述
树可以看成是一个连通且 无环 的 无向 图。
给定一个图该图从一棵 n 个节点 (节点值 1n) 的树中添加一条边后获得。添加的边的两个不同顶点编号在 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.length3 n 1000edges[i].length 21 ai bi edges.lengthai ! biedges 中无重复元素给定的图是连通的
解题思路
核心分析
这道题是一个经典的并查集应用问题。核心思想是找到导致图中出现环的那条边。
问题本质给定一个包含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 []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]}
}时间复杂度分析
每条边最多处理一次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, n1)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] 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²) 空间复杂度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] rootXuf.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)
}扩展思考
多条冗余边如果有多条冗余边如何找到所有冗余边加权图如果边有权重如何找到权重最小的冗余边有向图如果是有向图如何检测环动态图如果图结构动态变化如何维护冗余边的信息最小生成树如何利用冗余边检测构建最小生成树
相关问题
685. 冗余连接 II有向图中的冗余连接547. 省份数量连通分量的计算200. 岛屿数量二维网格中的连通性684. 冗余连接无向图中的冗余连接261. 以图判树判断图是否为树
测试用例设计
// 基础测试用例
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)最优解实现简单需要理解并查集DFSO(n²)O(n)思路直观时间复杂度高BFSO(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, n1)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, n1)// 初始化并查集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, n1)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])
}
