2015/04/24

【C++】Disjoint Set (array)簡單函式




首先disjoint set簡而言之就是說,有多個小圈圈,每一個小圈圈都有一個頭頭。

宣告 

?
1
int set[MAX];


make_set (讓每一個人在的小圈圈的頭頭都是自己,也就是有多少人就有多少個頭頭和小圈圈)

?
1
2
3
4
void make_set(){
    for (int i=1; i<=n; i++)
        set[i] = i;
}

union_set (把兩個小圈圈合在一起,一個小圈圈裡面的人的頭頭都變成另一個小圈圈的頭頭)

?
1
2
3
4
5
6
7
8
9
void union_set(int a, int b){
    if (set[a] != set[b]){
        int x = set[a], y =  set[b];
        for (int i=1; i<=n; i++) {
            if (set[i]==x)
                set[i] = y;
        }
    }
}

find_set (找到這個人所在的小圈圈的頭頭是誰)

?
1
2
3
void find_set(int x){
    return set[x];
}

---------------------------------------------------------

如果你想要同時計算每個小圈圈裡面有多少人

宣告

?
1
int set[MAX], num[MAX];

make_set

?
1
2
3
4
5
6
void make_set(){
    for (int i=1; i<=n; i++){
        set[i] = i;
        num[i] = 1;
    }
}

union_set 

?
1
2
3
4
5
6
7
8
9
10
11
12
void union_set(int a, int b){
    if (set[a] != set[b]){
        int x = set[a], y =  set[b];
        num[set[a]] = 0;
        for (int i=1; i<=n; i++) {
            if (set[i]==x){
                set[i] = y;
                num[set[b]]++;
            }
        }
    }
}

find_set不變