文章目錄
- 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 []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, 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] = 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(n2)
空間復雜度：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))
執行流程圖
算法可視化
實際應用
- 網絡拓撲設計：檢測網絡中的冗余連接
- 電路設計：識別電路中的冗余線路
- 社交網絡分析：發現社交網絡中的冗余關系
- 數據庫設計：檢測數據庫中的冗余約束
- 軟件架構：識別模塊間的冗余依賴
算法優化技巧
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) | 最優解，實現簡單 | 需要理解并查集 |
| DFS | O(n2) | O(n) | 思路直觀 | 時間復雜度高 |
| BFS | O(n2) | 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(n2)，空間復雜度：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(n2)，空間復雜度：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]")
}
