描述
給定一系列集合 \(\{1\}, \{2\}, \dots, \{n\}\) 和三類指令，指令一形如 \(1\;\;p\;\;q\)，若 \(p\) 和 \(q\) 屬同一集合，無視該指令，否則將 \(p\) 所屬集合和 \(q\) 所屬集合合併；指令二形如 \(2\;\;p\;\;q\)，若 \(p\) 和 \(q\) 屬同一集合，無視該指令，否則將 \(p\) 移動至 \(q\) 所屬集合；指令三形如 \(3\;\;p\)，輸出 \(p\) 所屬集合之元素個數及元素和。實作能以三類指令操作一系列集合的資料結構。
思路
題目已經提到併查集（union-find，後以不交集 disjoint-set 稱之），而且規定的指令確實跟不交集相關，沒有欺詐，因此實作不交集即可。以下 \(P\) 和 \(Q\) 分別表示 \(p\) 和 \(q\) 的所屬集合，\(r_p\) 和 \(r_q\) 分別為 \(P\) 中所有元素和 \(Q\) 中所有元素的代表，並且 \(r_p \in P\) 和 \(r_q \in Q\)，默認以不交集森林（disjoint-set forest）作為儲存所有集合的結構。
指令一
指令一為標準的 union 方法，無特別之處，先利用 find 方法找到 \(r_p\) 和 \(r_q\)，再比較 \(r_p\) 和 \(r_q\) 就可知道 \(p\) 和 \(q\) 是否屬同一集合，若非屬同一集合，要固定將一方併入另一方，或採按秩合併（union by rank），端看個人喜好。
指令二
指令二不屬於不交集原有的操作，確定 \(p\) 和 \(q\) 是否屬同一集合的方法同指令一，在確定兩者非屬同一集合後，若 \(p \neq r_p\)，也就是 \(p\) 不為森林中某棵樹的根節點時，此時只需將 \(p\) 的代表設為 \(r_q\) 即可，但倘若 \(p = r_p\)，也就是 \(p\) 為森林中某棵樹的根結點時，將 \(p\) 的代表設為 \(r_q\) 相當於將 \(P\) 併入 \(Q\) 中，而非只是簡單的移動，為了解決這個問題，至少有以下兩種思路。
- 先從 \(P\) 中找非 \(p\) 的元素 \(x\) 作新代表，並把 \(P\) 中所有非 \(p\) 元素的代表更新為 \(x\) ，再將 \(p\) 的代表設為 \(r_q\)。
- 使所有元素的代表都為不可移動的元素，如此一來就不會發生 \(p = r_p\) 的情況。
不難發現 1. 需要 \(|P| - 1\) 次操作，一般情況下 \(|P| < n\)，以森林來說應該還是可接受的。
至於要如何構造 2. 中的不可移動元素呢？其實方法很多很簡單，例如因為 \(n\) 的上限為 \(10,0000\)，可以使用 \(10,0000\) 以上的數字為不可移動元素，舉例來說，將初始集合 \(\{1\}, \{2\}, \dots, \{n\}\) 轉化為 \(\{10,0001, 1\}, \{10,0002, 2\}, \dots, \{10,0000+n, n\}\)，並以超過 \(10,0000\) 的數字作為代表，規避 \(p = r_p\) 的情況，因為 \(p\) 不可能會是 \(10,0000\) 以上的數字。
如果不喜歡 \(10,0000\) 以上的數字，也可以用負數作代表，形如 \(\{-1, 1\}, \{-2, 2\}, \dots, \{-n, n\}\)，原理相同，記得別將不可移動元素計入元素個數和元素和。這種方法雖然會讓空間增加一倍，但如果使用按秩合併和路徑壓縮（path compression，跟 find 方法有關），直覺告訴我這可以像 union 方法和 find 方法一樣在近似 \(O(1)\) 的平均時間完成，反正一定比 1. 快。
指令三
指令三為計算元素數量及元素和，無特別之處，在進行指令一或指令二時，順便維護各個集合的元素個數和元素和，遇指令三找到 \(r_p\) 後就可直接得到答案。
結論
不交集是種高效的資料結構，是 Kruskal 演算法的重要組成部分，假設以紅黑樹（red-black tree）模擬單個集合，則 union 需要 \(|P|\) 次對 \(P\) 的刪除和對 \(Q\) 的插入，也就是需要大約 \(|P| \times (O(log\;|P|) + O(log\;|Q|))\) 的平均時間，假設以雜湊表（hash table）模擬單個集合，則 union 需要大約 \(|P| \times (O(1) + O(1))\) 的平均時間，但使用按秩合併和路徑壓縮的不交集森林只需 \(O(\alpha(n)) \approx O(1)\) 的平均時間，因此雖然沒實際測試過，不過我認為用多個紅黑樹或雜湊表模擬所有集合是很有可能拿到 TLE 認證的。