題目描述: 有 n 個人和一組限制條件(restrictions),每個限制 [x, y] 表示 x 和 y 不能屬於同一個朋友群組。依序處理一系列交友請求(requests),每個請求 [u, v] 嘗試讓 u 和 v 成為朋友。若合併 u 和 v 的群組不會違反任何限制,則接受;否則拒絕。
解題思路: 使用 Union-Find(並查集)管理朋友群組。
對每個交友請求 [u, v]:
注意:不能先合併再檢查,因為一旦合併就無法撤銷(Union-Find 不支援 undo)。
時間複雜度:O(q * r * α(n)) — q 為請求數量,r 為限制數量,α(n) 為反阿克曼函數(Union-Find 操作的均攤複雜度)。
空間複雜度:O(n) — Union-Find 的 parent 和 rank 陣列。
1. Initialize Union-Find with n elements.
2. For each request [u, v]:
a. ru = find(u), rv = find(v).
b. If ru == rv: accept (already friends).
c. Else, for each restriction [x, y]:
- rx = find(x), ry = find(y).
- If {rx, ry} == {ru, rv}: reject (would violate restriction).
d. If no violation found: union(ru, rv), accept.
e. Record result.
3. Return results.可撤銷 Union-Find:先合併,然後檢查所有限制。若違反則撤銷合併。需要使用按秩合併(不做路徑壓縮)來支援撤銷。時間複雜度相同但常數因子較大。
圖著色 / 二分圖檢測:將限制視為「不能同色」的約束,每次請求等於嘗試合併兩個顏色群組。但本質上與 Union-Find 方法相同,只是換了一種思考角度。