不相交集合資料結構

題目敘述

不相交集合（又稱 union-find）把一堆元素分成彼此不重疊的集合，常用來處理「兩個東西是否已經被連在一起」這類問題。請實作這個資料結構，支援合併兩個集合、查詢某元素所屬集合的代表元，並在 find 時做路徑壓縮、合併時依秩或大小接樹，讓每個操作的攤銷成本接近常數。

請提交 dsu.h 與 dsu.c，介面如下：

typedef struct dsu dsu;

void dsu_init(dsu *d, int n); /* elements 0..n-1 */
int dsu_find(dsu *d, int x); /* representative */
void dsu_union(dsu *d, int a, int b);
int dsu_connected(dsu *d, int a, int b);
int dsu_count(dsu *d); /* number of disjoint sets */

評測用的驅動程式會先讀入操作數 Q，再依序執行 init n、find x、union a b、connected a b、count 這五種操作。

輸入格式

• 第 1 行：Q，操作的數量。
• 接下來 Q 行：每行是 init n、find x、union a b、connected a b、count 其中之一。

輸出格式

查詢類操作（find、connected、count）各輸出一行。

限制

• 1 ≤ Q ≤ 2 · 10⁵
• init n 中 1 ≤ n ≤ 10⁵
• 每次 init 之後，元素編號為 0, 1, …, n − 1

範例

範例 1

輸入

4
init 5
union 0 1
connected 0 1
count

輸出

1
4

init 5 先建立 5 個各只含一個元素的集合 {0}, {1}, {2}, {3}, {4}，union 0 1 把其中兩個併起來，剩 4 個集合。因此 connected 0 1 輸出 1，count 輸出 4。

範例 2

輸入

3
init 1
find 0
count

輸出

0
1

只有一個元素時，它自己就是代表元，所以 find 0 輸出 0，count 輸出 1。

範例 3

輸入

5
init 4
union 0 1
union 2 3
connected 1 2
count

輸出

0
2

兩次 union 之後集合是 {0, 1} 與 {2, 3}；1 和 2 不在同一個集合，所以 connected 1 2 輸出 0，count 輸出 2。

範例 4

輸入

6
init 3
union 0 1
union 1 2
count
init 2
count

輸出

1
2

前兩次 union 把 0, 1, 2 併成一個集合，第一個 count 輸出 1。第二次 init 2 會把整個結構重設成元素 0, 1 的兩個單元素集合，之前的合併不能留下來，所以第二個 count 輸出 2。

提示

• find 要做路徑壓縮（遞迴時寫回 p[x] = dsu_find(p[x])，或用迭代兩趟走訪）。否則連續的 union 可能讓樹變成長鏈，每次 find 都要 O(n)，大型測資會逾時。
• union 要比較兩棵樹的秩或大小，把小的接到大的底下；固定把第二個參數接到第一個底下，很容易造出長鏈。
• dsu_count 請隨合併增量維護（真的合併了兩個不同集合才減一），不要每次重新掃描。
• 若 a 與 b 已在同一集合，union a b 什麼都不做，dsu_count 不變。
• 每次 init n 都要完整重設為 n 個全新的單元素集合，不可沿用之前的狀態。