HardRating 1869
924. Minimize Malware Spread
arrayhash-tabledepth-first-searchbreadth-first-searchunion-findgraph
解題說明
Minimize Malware Spread
題目描述： 給定 n 個節點的網路圖（鄰接矩陣）和一組初始感染節點 initial。移除 initial 中的一個節點（使其不再被感染），使得最終感染節點數最少。如果有多個答案，返回索引最小的。
解題思路：
- Union-Find / DFS 找連通分量：先用 Union-Find 或 DFS 找出所有連通分量。
- 感染傳播規則：一個連通分量中如果有任何一個初始感染節點，整個分量都會被感染。
- 移除一個初始感染節點只有在該分量中恰好只有它一個感染源時才有效（否則其他感染源仍會感染整個分量）。
- 因此，我們要找：在連通分量中恰好只有一個初始感染節點，且分量大小最大的那個感染節點。移除它能「拯救」最多節點。
- 如果沒有這樣的分量，移除任何一個初始節點都不會改變結果，返回最小索引。
C++ 解法
複雜度分析
時間複雜度：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 remove其他解法
-
DFS 找連通分量：用 DFS 代替 Union-Find。先做一次完整的連通分量標記，然後對每個分量統計初始感染數和分量大小。邏輯相同，只是實作方式不同。
-
暴力模擬：逐一嘗試移除每個初始感染節點，對每種情況做 BFS/DFS 模擬感染傳播，統計最終感染數。時間複雜度 O(|initial| * n^2)，在 n 較小時可行。
延伸思考
- 如果可以移除 k 個初始感染節點而不是只能移除一個，如何選擇？
- 感染傳播如果有概率（不一定 100% 感染相鄰節點），問題會如何變化？
- 與 928 題（Minimize Malware Spread II）相比，差異在哪裡？