首先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不變
