題目描述:給定一個有 n 個節點(標號 1 到 n)的無向圖,由 n 條邊組成。由於比樹多了一條邊,圖中必有一個環。回傳最後一條造成環的邊(若有多條候選,回傳在輸入中出現最晚的那條)。
解題思路:使用**Union-Find(並查集)**逐一處理每條邊。初始時每個節點是各自的集合。對每條邊 (u, v):若 u 和 v 已在同一集合中,代表加上這條邊會形成環,這條邊就是答案;否則將兩個集合合併(union)。使用路徑壓縮(path compression)和按秩合併(union by rank)使每次操作接近 O(1)。
時間複雜度:O(n × α(n)) — 對 n 條邊各執行一次 find/union,α 為反阿克曼函數,實際上接近 O(1),整體近似 O(n)。
空間複雜度:O(n) — parent 和 rank 陣列各需 O(n) 空間。
1. Initialize Union-Find: parent[i] = i, rank[i] = 0 for all i in [1..n] 2. Define find(x): return root with path compression 3. Define unite(x, y): a. If find(x) == find(y): return false (cycle detected) b. Else merge by rank, return true 4. For each edge (u, v) in order: a. If unite(u, v) == false: return [u, v] 5. Return [] (should not reach here per problem guarantee)
DFS 環偵測 O(n):對圖做 DFS,若遇到已訪問的節點(非父節點)則找到環。但確認「哪條邊是最後加入的」需要額外處理,不如 Union-Find 直觀。
拓撲排序(去葉節點)O(n):反覆移除度數為 1 的節點,剩下的節點就構成環。環上最後出現的邊即為答案。邏輯較迂迴,適合特定變體題型。