1319. Number of Operations to Make Network Connected
解題說明
Number of Operations to Make Network Connected
題目描述：有 n 台電腦（編號 0 到 n-1）和 m 條網路線（edges）連接部分電腦。每次操作可以拔掉一條已存在的網路線，重新插到任何兩台電腦之間。求最少需要幾次操作，才能使所有電腦都連通；若無法做到，回傳 -1。
解題思路：
數學直覺：要讓 n 個節點全部連通，至少需要 n-1 條邊（形成一棵生成樹）。若 edges < n-1，邊的數量根本不夠，直接回傳 -1。
Union-Find 主流程：
- 初始化 n 個連通分量。
- 依序處理每條邊：
- 若兩端已在同一分量（冗餘邊）：
redundant++，這條邊可以被「借用」。 - 否則：union 兩端，
components--。
- 若兩端已在同一分量（冗餘邊）：
- 最終有
components個獨立分量，需要components - 1條邊將它們橋接起來。 - 只要
redundant >= components - 1，就有足夠的邊可以重新插接，回傳components - 1。
為何冗餘邊一定足夠：已在第一步驗證 edges >= n-1。每個連通分量至少有 1 條邊（除非分量只有 1 個孤立節點）。可以數學證明：edges >= n-1 保證 redundant >= components - 1（冗餘邊至少等於需要橋接的分量間隔數）。
答案：若 edges < n-1，回傳 -1；否則回傳 components - 1（連通分量數 - 1）。
C++ 解法
複雜度分析
時間複雜度：O(m · α(n)) ≈ O(m) — 對 m 條邊各執行一次 unite（含兩次 find），每次 O(α(n)) 接近常數。整體接近線性 O(m)。
空間複雜度：O(n) — parent 和 rank 陣列各長 n。
虛擬碼
1. If edges.size() < n-1: return -1 // impossible, not enough cables 2. Initialize Union-Find: parent[i]=i, rank[i]=0, components=n 3. For each edge [a, b]: If unite(a, b) returns true: components-- // Else: redundant edge (already in same component) 4. Return components - 1 // We need exactly (components-1) bridge operations
其他解法
DFS/BFS 計算連通分量 O(n + m)：建立鄰接表，用 DFS/BFS 統計連通分量數 c 和冗餘邊數 r（邊數 - (n - c)）。同樣先判斷 m < n-1 回傳 -1，否則回傳 c - 1。優點是思路更直觀（分兩步：數連通分量數、數多餘邊）；缺點是需要建圖的額外空間 O(n + m)，而 Union-Find 只需 O(n)。
Kruskal MST 視角：本題等價於 Kruskal 算法中找最小生成樹：只選 n-1 條邊連通所有節點，多餘邊數 = m - (n-1) 個邊（在無環情況下）。需要的操作數 = 連通分量數 - 1。兩種觀點殊途同歸，Union-Find 同時完成了「找連通分量」和「統計冗餘邊」兩件事。
暴力 BFS 重複檢查 O(m·(n+m))：每次拔掉一條邊後重新 BFS 確認連通性，選擇效益最大的操作。完全沒有必要，因為不需要知道具體拔哪條邊，只需知道數量，時間複雜度也極差，僅適合理解問題。
延伸思考
- 若每條網路線有「拔除成本」，求最小總成本使網路連通，這是什麼問題？（提示：最小生成樹，Kruskal/Prim）
- 本題保證
edges.size() >= n-1時答案一定可行（即冗餘邊一定夠用），請用數學方式嚴格證明這個結論。 - 若不僅要讓圖連通，還要讓圖是 2-edge-connected（任意移除一條邊後仍連通），最少需要加多少條邊？