並查集

目標

判斷連通 , 找兩個點有沒有在同個集合裡面 ( 有同個father,血緣關係 )

實作

準備一個 陣列 存根節點 並把根結點 設為自己

製作兩個 funtion

• 查找 Find
• 合併 Union

透過查找是否屬於同個 "根" 相不相同 就可以知道關係

優化?

因為 無腦的合併 會出現 很長一條鏈 -> 在搜尋的時候就會非常花時間
解決方法:

• 紀錄每集合的高度 -> 把矮的樹 並到 高的樹裡面 (有點像在幫樹做平衡)
• 每次查找的時候 把結果再存回去

Pseudocode:

vector<int> f,Rank;   // f存根節點 Rank存高度

void UFinit(int V){
    f.resize(V+1);  
    Rank.resize(V+1);
    for(int i=0;i<=V;i++)
        f[i] = i;
}

int Find(int x){
    return x == f[x] ? x : f[x] = Find(f[x]);
}

void Union(int x,int y){
    if (Rank[x] < Rank[y])
        pa[x] = y;
    else{
        if (Rank[x] == Rank[y])
            Rank[x]++;
        pa[y] = x;
    }
}

應用:

Kruskal 算法