【筆記】Disjoint Set Union-find algorithm (DSU) 並查集

  • 【用途】並查集是一種資料結構,用於處理不相交集合(Disjoint Sets)的合併及查詢。操作時使用Union-Find algorithm。
  • 【原理】
    • 資料結構:有向圖
    • 每個點有一個出邊(out-degree) 代表每個頂點所屬集合的「代表元素」,初始值指向自己。
    • 查詢時如果遇到指向自己的點 x,則 x 即為該集合的代表元素,回傳 x,否則繼續查詢。
  • 【實作1】
    • 初始化陣列 p[i] = i,表示指向自己。
    • Find( ):找出目標元素屬於哪一個集合 。【版本2】 順便進行路徑壓縮(邊的縮減),可縮短後續查詢的時間。
    • Union( ):把兩個集合合併成一個。
  • 【實作2】 可連帶查詢集合的成員數目
    • 初始化陣列 p[i] = -1,表示指向自己。
    • p[代表元素] = 集合內的成員數目(負數)。
    • 當 i 不是所屬集合的代表元素時,p[i] = 代表元素編號。
  • 【範例】ZeroJudge a445: 新手訓練系列- 我的朋友很少
  • 【範例】ZeroJudge d831: 畢業旅行
  • 【練習】ZeroJudge d449: 垃圾信件

【實作1】

//版本-1
int Find(int x){
    // 當p[x] = x,x 即為該所屬集合的代表元素
    // 否則遞迴繼續找
    return p[x] == x ? x : Find(p[x]);
}

//版本-2: 路徑壓縮
int Find(int x){
    // 當p[x] = x,x 即為該所屬集合的代表元素
    // 否則遞迴繼續找,順便做「路徑壓縮」
    return p[x] == x ? x : p[x] = Find(p[x])
}

void Union(int x,int y){
    int g1 = Find(x); //找出x所屬集合的代表元素
    int g2 = Find(y); //找出y所屬集合的代表元素
    if(g1 != g2) p[g2] = g1; //將g2指向g1,即為合併兩個集合,g1為代表元素
}

【實作2】可連帶查詢集合的成員數目

int Find(int x){    
    // 初始值 p[x] = -1 表示指向自己
    return p[x] < 0 ? x : p[x] = Find(p[x]);
}

void Union(int x, int y){
    int g1 = Find(x);
    int g2 = Find(y);
    if(g1 != g2){
        p[g1] += p[g2]; //加總元素個數(負值)
        p[g2] = g1; //p[]:只有代表元素的值是存元素個數,其它的存代表元素編號
    }
}
分享本文 Share with friends