題目描述: 有 n 個人,0 號和 firstPerson 在時間 0 知道秘密。有一系列會議 [x, y, time],表示 x 和 y 在時間 time 見面。若其中一人知道秘密,另一人也會知道。秘密在同一時間的所有會議中可以傳遞性地傳播。求最終所有知道秘密的人。
解題思路: 按時間分組處理會議,使用 Union-Find。
關鍵:同一時間的會議形成若干連通分量。只有與已知秘密者連通的分量才會獲知秘密。其他分量需要回滾。
時間複雜度: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 波)。