1101. The Earliest Moment When Everyone Become Friends
解題說明
The Earliest Moment When Everyone Become Friends
題目描述:有 n 個人(編號 0 到 n-1)。給定一個 logs 陣列,每條記錄為 [timestamp, x, y],表示在時間點 timestamp,x 和 y 成為朋友(友誼具有傳遞性:若 a-b 是朋友,b-c 是朋友,則 a、b、c 都互相認識)。找出最早的時間點,使得所有人都互相認識(即全部在同一個「認識」連通分量中);若不存在這樣的時間點,回傳 -1。
解題思路:
本題是標準的 Union-Find 應用,目標是找出讓整個圖連通的最早時刻。
關鍵步驟:
- 排序:
logs不一定按時間順序排列,需先對timestamp升序排序,確保我們按時間順序處理友誼關係。 - 逐步 Union:對排序後的每條記錄,執行
union(x, y)。若 union 成功(兩人原本不在同一分量),將連通分量計數components--。 - 終止條件:當
components == 1時,說明所有人已互相認識,回傳當前timestamp。 - 無解情況:若處理完所有 logs 後
components > 1,回傳 -1。
初始狀態:n 個人初始有 n 個獨立連通分量,目標是讓分量數降為 1。
C++ 解法
複雜度分析
時間複雜度:O(m log m + m · α(n)) ≈ O(m log m) — 主要開銷在排序(m 為 logs 數量,O(m log m));之後 m 次 union 操作各 O(α(n)) 接近常數,整體由排序主導。
空間複雜度:O(n) — parent 和 rank 陣列各長 n;排序使用 O(log m) 的遞迴棧空間(標準庫排序)。
虛擬碼
1. Sort logs by timestamp (ascending) 2. Initialize Union-Find: parent[i]=i, rank[i]=0, components=n 3. For each log [t, x, y] in sorted order: a. If unite(x, y) returns true: components-- b. If components == 1: return t 4. Return -1
其他解法
BFS/DFS 時間軸掃描 O(m log m + m·n):同樣排序後逐步加邊建圖,每次加邊後用 BFS/DFS 重新計算連通分量數。優點是不需要 Union-Find 知識;缺點是每次加邊後的 BFS/DFS 需要 O(n + m) 時間,整體 O(m·n),遠慢於 Union-Find 的 O(m log m)。
二分搜尋答案 + BFS/DFS 驗證 O(m log² m):二分搜尋時間戳,對每個候選時間點取所有時間 ≤ t 的 logs 建圖,BFS/DFS 驗證是否全連通。優點是不需要 Union-Find;缺點是每次驗證 O(m + n),整體 O(m log m · log m),不如直接掃描效率高,且實作更複雜。
Kruskal 思路(等效):本題本質上等同於 Kruskal 最小生成樹中找到讓圖連通的最後一條邊的權重(這裡的「邊權」為時間戳)。理解這個等價性後,可以直接套用 Kruskal 框架:按邊權排序,依序加邊直到 MST 完成(即所有節點連通),回傳最後加入的邊的權重。與上述實作完全等價,但提供了不同的思考視角。
延伸思考
- 若友誼可以「解除」(即 logs 中也可能有斷開連接的記錄),Union-Find 不支援分裂操作,應如何處理?(提示:Link-Cut Tree 或離線逆向處理)
- 若問題改為「最晚到什麼時間點,仍然存在某兩人互不認識」,答案如何快速求得?
- 本題若要求回傳所有讓全員連通的可能「最早時間點」(假設存在並列的時間戳),如何修改程式?