題幹與適用場景
給定 n 個使用者和 q 個按時間排列的操作。add id u v 在時間點加入一條帶 ID 的無向關係，remove id 刪除這條關係，ask u v 查詢兩人目前是否連通。每條關係最多新增和刪除一次，所有操作已知後才開始回答查詢。
題目要求輸出每個 ask 的布林結果。需要說明普通並查集為什麼無法安全處理刪除、如何把關係的存活時間映射到時間線、如何恢復狀態，以及邊界條件和複雜度。目標是離線動態連通性，不要求線上處理未來操作。
面試官考察點
- 能否識別「只增不減」的並查集不變量在刪除操作下失效。
- 能否把每條邊轉換成半開存活區間
[加入時間, 刪除時間)。 - 能否用時間線段樹把一個區間分解成
O(log q)個節點。 - 能否實作不做路徑壓縮、只按大小合併的 rollback DSU。
- 能否說明快照、遞迴返回和查詢結果之間的正確性關係。
回答前需要釐清的問題
- 所有操作是否提前可見？若必須線上回答，時間線段樹方案不適用。
- 關係是否有唯一 ID？沒有 ID 時需要定義刪除哪一條重複邊。
- 圖是否無向？若是有向圖，連通性結構和演算法都要改寫。
- 一條關係是否可能重複新增、刪除後再次新增？若允許，必須為每段存活期建立獨立區間。
- 查詢只問連通性，還要回傳元件大小、最短路或路徑？後者需要擴充狀態或更換演算法。
30 秒回答框架
普通並查集只能合併，不能在不知道內部樹結構影響的情況下刪除一條邊。我會先掃描操作，為每條邊建立存活區間 [add, remove)，未刪除的邊延伸到 q。把區間加入時間線段樹，DFS 進入節點時合併該節點涵蓋的所有邊，在葉子回答查詢，離開節點時回滾到進入前的快照。rollback DSU 不做路徑壓縮，只按大小合併，因此每次合併可記錄一次父節點和大小變化；總複雜度是 O((q log q) log n) 量級，空間為 O(n + q log q)。
分步驟深入解答
第一步：確認普通並查集的失效點
普通並查集維護的是目前所有已加入邊的合併結果。刪除邊時，某棵樹中的節點可能仍透過其他邊連通，也可能需要拆分整棵樹；僅憑父指標無法知道應恢復哪些元件。因此不能在普通並查集上直接呼叫「反向 union」。
第二步：建立邊的存活區間
掃描操作並記錄 add 時間。遇到對應 remove 時形成 [add, remove)；葉子時間 t 表示執行第 t 個操作前後的統一時刻，採用半開區間可避免刪除時刻仍誤用該邊。沒有刪除的關係形成 [add, q)。
第三步：用時間線段樹覆蓋區間
把每個存活區間放入線段樹中完全覆蓋它的節點。一個區間最多進入 O(log q) 個節點。節點中的邊在該節點整個時間範圍內都有效，所以進入節點時合併一次即可，不必在每個葉子重複處理。
第四步：設計可回滾 DSU
使用 parent 和 size 陣列。find 只沿父指標向上，不做路徑壓縮；union 把小樹掛到大樹，並把被修改的根、舊大小和元件數壓入堆疊。按大小合併保證樹高不超過 O(log n)。
第五步：DFS、快照和恢復
進入節點先保存堆疊長度 snapshot，再套用節點中的邊。到葉子執行該時間點的 ask。遍歷完子節點後，把堆疊彈回 snapshot。父節點的邊因此繼續對下一個子樹生效，子樹暫時加入的邊不會外洩。
第六步：實作核心
核心程式與中文版相同：先建存活區間，再把區間掛到時間線段樹；DFS 時以 rollback DSU 維護目前路徑上的邊。實作時要保留 find 不壓縮路徑、記錄舊 size，並在半開區間的葉子回答查詢。
第七步：證明不變量與複雜度
進入任意線段樹節點時，DSU 恰好包含覆蓋該節點整個時間範圍的邊，加上祖先節點已套用的邊。子節點新增的邊只存在於其子樹，返回時回滾，因此葉子時 DSU 等於該時刻所有存活邊的並集。每條邊進入 O(log q) 個節點，每次合併因按大小合併為 O(log n)，總時間 O(q log q log n)，歷史和邊儲存為 O(n + q log q)。
第八步：比較替代方案與失敗場景
若只有新增邊和連通查詢，普通並查集更簡單，攤還複雜度接近常數。若必須線上處理刪除，時間線段樹不能使用，應考慮動態樹或更複雜的全動態結構。若需要最短路，DSU 只能回答元件關係，不能替代 BFS、Dijkstra 或動態最短路演算法。
高品質示範回答
我會先確認操作全部已知且每條關係有穩定 ID。普通並查集只能合併，刪除會破壞它維護的元件不變量，所以我掃描操作得到每條邊的存活區間 [加入時間, 刪除時間)，未刪除的邊延伸到操作末尾。然後把區間放入時間線段樹：DFS 進入節點時合併節點中的邊，在葉子回答連通性查詢，離開節點時回滾到進入前的歷史堆疊長度。rollback DSU 不做路徑壓縮，只按大小合併並記錄父節點和舊大小，因此樹高是 O(log n)。每條邊進入 O(log q) 個節點，總時間 O(q log q log n)，空間 O(n + q log q)。如果只增不減，我會改用普通並查集；如果要求線上刪除或最短路，則需要換成更強的動態結構。
常見錯誤
- 直接對刪除邊做反向 union → 合併不可逆，無法知道要拆分哪些元件 → 改用存活區間和回滾。
- 在 rollback DSU 中使用路徑壓縮 → 修改路徑上的多個父指標卻沒有完整記錄 → 只按大小合併，
find不壓縮。 - 把區間寫成閉區間
[add, remove]→ 刪除時刻仍把邊算作存活 → 使用半開區間[add, remove)。 - 每個葉子重新合併所有邊 → 複雜度退化且失去線段樹意義 → 在覆蓋整個時間範圍的節點合併一次。
- 只恢復父節點不恢復
size→ 後續按大小合併的樹形被污染 → 每次修改記錄舊大小並一起恢復。 - 把離線方法承諾為線上方案 → 新操作到達後時間區間未知 → 先確認互動模型，再選擇資料結構。
追問及應對
如果同一個關係 ID 會被刪除後再次新增，怎麼改？
每次 add 都建立一條新的開放記錄，remove 只關閉目前未關閉的那一段。同一 ID 因而會產生多個不重疊區間，不能覆蓋舊區間或重用同一個起點。
如果還要查詢目前連通元件大小，能否重用方案？
可以在 DSU 中維護根的 size，find 回傳根後讀取大小；回滾時恢復舊大小。若還要維護元件數或聚合值，也要把每次可變欄位的舊值壓入堆疊，並確保聚合操作可逆。
如果 q 很大、遞迴深度或記憶體成為瓶頸，怎麼辦？
先確認 O(q log q) 的區間儲存是否可接受，再用顯式 DFS 堆疊取代遞迴、壓縮邊結構或按時間區塊處理。不能因為堆疊溢位就啟用路徑壓縮，應保持可回滾不變量。
如果必須線上支援刪除，為什麼不能把區間方案硬改成線上？
區間方案要知道一條邊何時刪除，才能把它放進時間線段樹。線上場景中未來刪除時間未知，預處理階段無法建立完整區間；應改用支援刪除的動態連通性結構，重新評估實作複雜度和查詢延遲。