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 的合併策略需要怎麼調整？
若要求輸出每個人最早知道秘密的時間，需要記錄什麼額外資訊？

Find All People With Secret — CaffeCode