MediumRating 1893
3608. Minimum Time for K Connected Components
binary-searchunion-findgraphsorting
解題說明
Minimum Time for K Connected Components
題目描述：給定一個 n 個節點的無向圖，每條邊有一個「移除時間」。隨著時間推進，到達移除時間的邊會被移除。問最少需要多少時間，使得圖中的連通分量數量達到至少 k 個。
解題思路：反向思考 — 時間越大，被移除的邊越多，連通分量越多。因此連通分量數量對時間具有單調性（非遞減）。可以對時間進行二分搜尋。對於一個候選時間 t，保留所有移除時間 > t 的邊，用 Union-Find 計算連通分量數。若連通分量 >= k，則 t 可行，嘗試更小的 t；否則需要更大的 t。
也可以用排序的方法：將邊按移除時間排序，從小到大移除邊。初始連通分量為 1（假設圖連通），每移除一條橋邊時連通分量增加。但二分搜尋方法更直觀且正確。
C++ 解法
複雜度分析
時間複雜度：O(E log E * α(V)) — 排序邊 O(E log E)，二分搜尋 O(log E) 層，每層用 Union-Find O(E * α(V))。
空間複雜度：O(V + E) — Union-Find 陣列和邊列表。
虛擬碼
1. Collect all unique edge removal times, sort them 2. Binary search on these times: a. For candidate time t, keep only edges with removal_time > t b. Use Union-Find to count connected components c. If components >= k: t is feasible, try smaller d. Else: need larger t 3. Return the minimum feasible time
其他解法
逐步移除邊（排序法） O(E log E + E * α(V))：將邊按移除時間排序，從後往前用 Union-Find 加入邊。反過來看，就是從全連通開始逐步移除邊，記錄何時連通分量達到 k。可以避免二分搜尋的重複計算。
暴力模擬 O(T * E)：枚舉每個時間點，重新計算連通分量。在時間範圍大時效率很差。
延伸思考
- 如果邊不僅會被移除還會被添加，如何動態維護連通分量數？
- 若要求恰好 k 個連通分量（而非至少 k 個），問題是否有解的保證？
- 若某些節點也有移除時間，如何同時處理節點和邊的移除？