主題
題目連結：
題目大意：
輸入有多筆測試資料。每筆第一列給定兩正整數 N 、 M （1 ≦ N 、 M ≦ 100000），代表有 n 個人，編號為 1 ～ n，並且要對他們做 M 次操作。
接著有 M 列輸入，每列代表一種操作。操作的開頭會給定一整數，代表是何種指令，格式如下：
1 P Q：將編號 P 與編號 Q 兩人所在的群體合併成同一個。
2 P Q：將編號 P 的人移出原本的群體並加進到編號 Q 在的群體（如果 P 和 Q 為同一群體則忽略）。
3 P：輸出編號 P 所在的群體之成員個數以及各個成員編號之總和。
範例輸入：
5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3
範例輸出：
3 12
3 7
2 8
解題思維：
很像一般的併查集（Union-Find Set）之題型，但是稍微變化。可以參考原本的併查集，如這題。
對於本題，本來併查集會使用的 ranks 可以作為該群體之成員個數。而總和也可以仿照 ranks 的做法，用 sums[i] 代表編號 i 在的群體之編號總和。
只是當在初始化編號 i 的變數時，ranks[i] 是設為 1 （自己只占 1 個人的位置），但是 sums[i] 要設為 i （自己的編號之值為 i）。
那麼移除呢？實際上，你只需要將 sums[FindParent(P)] 減去 P 、rank[FindParent(P)] 減去 1 即可達成「移除」的結果，並不須要更動 parents 陣列（可以維持原樣）。
但是不改變 parents 可能會與後面的操作衝突，那麼 P 要怎麼加進 Q 在的群體呢？你可以給 P 一個新的「編號」（N + 1 、 N + 2 等等，頂多到 N + M），然後將新的編號按照正常方式去跟 Q 聯集。
因此，我們還需要一個陣列 mapping 紀錄每個數字的映射。一開始對於每個數字 i （1 ≦ i ≦ n），mapping[i] ＝ i 。
但是記得賦予新編號的時候要初始化 sums[新編號] ＝ P （雖然名目上的編號變了，但是題目要的總和是原本的編號）、 Ranks[新編號] ＝ 1。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
