題目描述: 給定 n 個節點的網路圖(鄰接矩陣)和一組初始感染節點 initial。移除 initial 中的一個節點(使其不再被感染),使得最終感染節點數最少。如果有多個答案,返回索引最小的。
解題思路:
時間複雜度:O(n^2) — 建立 Union-Find 需遍歷鄰接矩陣
空間複雜度:O(n) — Union-Find 的 parent 和 size 陣列
1. Build Union-Find from adjacency matrix
2. For each initial infected node, map its component root to the list of infected nodes in that component
3. Sort initial array
4. For each initial node:
a. If its component has exactly 1 infected node:
- Compare component size with best; update if larger (or smaller index on tie)
5. If no single-source component found, return smallest index in initial
6. Return the best node to removeDFS 找連通分量:用 DFS 代替 Union-Find。先做一次完整的連通分量標記,然後對每個分量統計初始感染數和分量大小。邏輯相同,只是實作方式不同。
暴力模擬:逐一嘗試移除每個初始感染節點,對每種情況做 BFS/DFS 模擬感染傳播,統計最終感染數。時間複雜度 O(|initial| * n^2),在 n 較小時可行。