HardRating 2004
2092. Find All People With Secret
depth-first-searchbreadth-first-searchunion-findgraphsorting
解題說明
Find All People With Secret
題目描述: 有 n 個人,0 號和 firstPerson 在時間 0 知道秘密。有一系列會議 [x, y, time],表示 x 和 y 在時間 time 見面。若其中一人知道秘密,另一人也會知道。秘密在同一時間的所有會議中可以傳遞性地傳播。求最終所有知道秘密的人。
解題思路: 按時間分組處理會議,使用 Union-Find。
- 將所有會議按時間排序並分組。
- 對每組同時間的會議:
- 用 Union-Find 將會議中的人合併。
- 合併完後檢查:若某群組中有人知道秘密(與 0 號連通),則該群組所有人都知道。
- 對於不與 0 號連通的群組,重置這些人的 Union-Find 狀態(撤銷合併),因為同時間內秘密只在連通的群組中傳播。
關鍵:同一時間的會議形成若干連通分量。只有與已知秘密者連通的分量才會獲知秘密。其他分量需要回滾。
C++ 解法
複雜度分析
時間複雜度:O(m log m + (m + n) α(n)) — 排序會議 O(m log m),Union-Find 操作總計 O(m α(n)),最終遍歷 O(n)。
空間複雜度:O(n + m) — Union-Find 陣列 O(n),會議分組的臨時陣列 O(m)。
虛擬碼
1. Initialize Union-Find for n people.
2. Unite person 0 and firstPerson.
3. Sort meetings by time.
4. Process meetings in groups of same time:
a. For each meeting [u, v, t] in this time group: unite(u, v). Track all involved people.
b. After processing all meetings at time t:
- For each involved person p: if find(p) != find(0), reset parent[p] = p.
5. Collect all people where find(p) == find(0).
6. Return result.其他解法
-
BFS/DFS 按時間層處理:按時間分組建圖,對每組會議建立臨時圖,從已知秘密的人做 BFS/DFS 傳播秘密。時間複雜度相同,但每組需要重新建圖,常數因子較大。
-
時序圖 + 多源 BFS:將所有會議按時間排序後,維護一個「已知秘密者」集合。按時間順序掃描,遇到會議時若參與者之一在集合中,加入另一人。需要處理同時間的傳遞性傳播(一次 BFS 波)。
延伸思考
- 若秘密有「時效性」,即知道秘密後超過 T 時間就會忘記,如何修改演算法?
- 若會議可以有多人(不只兩人),Union-Find 的合併策略需要怎麼調整?
- 若要求輸出每個人最早知道秘密的時間,需要記錄什麼額外資訊?