題目描述: 與 924 題類似,但這裡移除一個初始感染節點意味著將其從圖中完全刪除(斷開所有連邊),而不只是取消其感染狀態。求移除哪個初始節點能使最終感染數最少。
解題思路:
時間複雜度: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 方法相同,但使用不同的資料結構。