HardRating 1985
928. Minimize Malware Spread II
arrayhash-tabledepth-first-searchbreadth-first-searchunion-findgraph
解題說明
Minimize Malware Spread II
題目描述： 與 924 題類似，但這裡移除一個初始感染節點意味著將其從圖中完全刪除（斷開所有連邊），而不只是取消其感染狀態。求移除哪個初始節點能使最終感染數最少。
解題思路：
- 反向思考：先移除所有初始感染節點，在剩餘圖中找連通分量。
- 對於每個非感染的連通分量，看它與哪些初始感染節點相鄰。如果一個分量只與一個初始感染節點相鄰，那麼移除該感染節點就能拯救這個分量。
- 對每個初始感染節點，累加它能「獨自拯救」的分量大小。
- 選擇能拯救最多節點的初始感染節點。平手時選索引最小的。
C++ 解法
複雜度分析
時間複雜度：O(n^2) — 遍歷鄰接矩陣進行 BFS 和鄰居檢查
空間複雜度：O(n) — 連通分量標記和相關資料結構
虛擬碼
1. Mark all initial infected nodes 2. BFS to find connected components among non-infected nodes 3. For each component, find which infected nodes are adjacent to it 4. For each component adjacent to exactly ONE infected node: - Add component size to that infected node's savings 5. Among initial nodes, pick the one with maximum savings - Tie-break by smallest index 6. Return the best node
其他解法
-
暴力模擬：對每個初始感染節點，模擬移除它後的感染傳播過程。需要對每個候選做一次完整的 BFS/DFS。時間複雜度 O(|initial| * n^2)。
-
Union-Find 方法：先用 Union-Find 在非感染節點間建立連通分量，然後對每個感染節點檢查相鄰的分量。效率與 BFS 方法相同，但使用不同的資料結構。
延伸思考
- 924 題和 928 題的核心差異是什麼？在什麼情況下它們的答案會不同？
- 如果圖是動態變化的（邊會被新增或刪除），如何高效維護答案？
- 如果可以移除 k 個感染節點，這個問題的最佳算法是什麼？