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 應用，目標是找出讓整個圖連通的最早時刻。

關鍵步驟：

1. 排序：logs 不一定按時間順序排列，需先對 timestamp 升序排序，確保我們按時間順序處理友誼關係。
2. 逐步 Union：對排序後的每條記錄，執行 union(x, y)。若 union 成功（兩人原本不在同一分量），將連通分量計數 components--。
3. 終止條件：當 components == 1 時，說明所有人已互相認識，回傳當前 timestamp。
4. 無解情況：若處理完所有 logs 後 components > 1，回傳 -1。

初始狀態：n 個人初始有 n 個獨立連通分量，目標是讓分量數降為 1。

時間複雜度：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) 的遞迴棧空間（標準庫排序）。

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 完成（即所有節點連通），回傳最後加入的邊的權重。與上述實作完全等價，但提供了不同的思考視角。

1. 若友誼可以「解除」（即 logs 中也可能有斷開連接的記錄），Union-Find 不支援分裂操作，應如何處理？（提示：Link-Cut Tree 或離線逆向處理）
2. 若問題改為「最晚到什麼時間點，仍然存在某兩人互不認識」，答案如何快速求得？
3. 本題若要求回傳所有讓全員連通的可能「最早時間點」（假設存在並列的時間戳），如何修改程式？