演算法知識 - Disjoint Set 並查集

Disjoint Set 介紹與應用

Disjoint Set 並查集是資料結構的其中一種，主要用來處理元素間的合併與查詢，並查集有 2 種操作

• 查詢 查詢某個元素是在哪個集合中，通常是返回集合內的代表元素，也就是在查詢此集合中的任一元素時，都會傳回此元素
• 合併 將兩個集合合併成一個

由於此兩操作時間複雜度都是 \(O(\log_n\)，且編寫容易，因此受到大量地使用，是個很棒的資料結構

Disjoint Set 原理

建立初始 Disjoint Set

由於一開始每個元素都是獨立的集合且也是自己集合中的代表元素，因此先寫一個迴圈讓每個元素都是集合中的代表元素。

#define MAXN 2000
void init(){
    for(int i = 0; i < MAXN; i++){
        tree[i] = i;
        cnt[i] = 1; //cnt 為數量，也就是每一個集合的數量，一開始都是 1，因為只有自己。
    }
}

查詢

查詢是要查詢某個元素是在哪個集合中，因此我們只需要寫這樣即可。

int find_root(int i){
    if(tree[i] != i) //如果 tree[i] 本身並不是集合中的代表元素，
    //表示這個集合中有其他元素，並且其他元素才是代表元素
        return tree[i] = find_root(tree[i]); //遞迴，將 tree[i] 的元素在進行查詢，
        //並將代表元素設為現在的 tree[i]
    return tree[i]; //回傳代表元素
}

合併

合併較為簡單，只需要先查詢 tree[a],tree[b] 這兩個的代表元素是否為一樣，如果不一樣就表示兩個為不同集合，讓 tree[b]代表元素與tree[a]相同即可，這樣之後在查詢中代表元素就會相同。

計算數量的陣列也要進行改變，因為這兩個集合被合併了，因此數量要進行更新，讓 cnt[b] 的值加給 cnt[a]， cnt[b] 之後再將他歸 0。

void merge(int a, int b){
    rx = find_root(tree[a]); //找出 find_root(tree[a]) 的代表元素
    ry = find_root(tree[b]); //找出 find_root(tree[b]) 的代表元素
    if(rx != ry) //如果不一樣就合併
        tree[ry] = rx; //要合併的是代表元素，不是 tree[b]
        cnt[rx] += cnt[ry]; //將原本另一集合的數量加到這集合，因為他們合併了
        cnt[ry] = 0;  //由於合併，因此將原本獨立的集合數量歸 0
}

QUESTION: 可能有些人會想問這樣真的就可以合併成功嗎？

我知道大家好奇的原因，因為我也好奇過XD。

可是我們稍微思考一下，由於我們是將 tree[ry] 的代表元素更換為 tree[rx] 的代表元素，因此在查詢到 tree[ry]，就會發現 tree[ry]已經不是代表元素了，因此會再進行一次遞迴，就會查詢到 tree[rx]，發現他是代表元素，就開始不斷的進行 return。

QUESTION: 可能還會有些人好奇那原本 tree[ry] 的集合中其他元素不還是指向 tree[ry] 嗎?沒關係嗎?

沒關係的，在查詢中一樣會先查詢到 tree[ry] 但它並不是代表元素，因此會在遞迴查詢，就會查到 tree[rx]，之後再遞迴回傳時在讓當前的 tree[i]直接指向代表元素即可，加快效率。

count 計算數量

disjoint set 常常會需要計算數量，這時我們前面使用的 cnt 陣列就派上用場了，用法很簡單，因為前面在合併的過程中都幫助我們處理好了。

cout << cnt[find_root(x)] ; // x 為要查詢的集合

QUESTION: 這樣真的就會計算數量成功嗎? 我們只有將兩個集合加入，但還會有點沒有被算到吧？

會的，因為每一次的合併都會將別人的元素加入，最一開始的合併一定是 1+1，也就是兩個點的合併，只要一開始是正確的，後面就都會正確。

不然就不叫程式了XD。

Disjoint Set 應用

• Uva11987 - Almost Union-Find (Disjoint Set)
• UVa599 - The Forrest for the Trees(Disjoint Set)
• UVa11503 - Virtual Friends(Disjoint Set)

參考連結

併查集

心得

這是我在高中時期就學會的演算法之一，在高職的時候我是自己學的，在新北市政府的幫助之下讓我去版中上課，接觸到了許多優秀的人才以及優秀的老師(蝸牛老師)，老師在教演算法這塊特別優秀，教導的十分好懂，是我的演算法啟蒙老師之一，很謝謝老師的講解！讓我在快要忘記之餘強制複習，才讓他完全記錄在我的腦海之中。