Union-Find (Disjoint-Set)

從 Disjoint-Set (DSU) 這個名字來看
這個資料結構是由許多 Set（集合） 所組成，並且彼此 Disjoint（互斥）
通常會用來解決 集合合併 和 集合查找 的問題

要點

功能

  • union：合併，將兩個集合合併為一個集合
  • find：查找某節點的根節點，用來確定該節點屬於哪一個集合

可以針對其他的需求實作
例如：size（查詢集合中有幾項元素）、sum（查詢集合的數值總和）

觀念

需要一個一維陣列用來記錄各個節點的父節點
初始化時，每個節點的父節點都是自己或是原本已指定好的圖
在隨著多次合併之後，可以利用遞迴函式查找到 a 和 b 節點的根節點來判斷是否在同一個集合內

實作細節

find

這邊除了直接查找根節點之外，同時還用了一種觀念就是 「路徑壓縮」
路徑壓縮也就是在查詢的過程中順便將所有經過的節點指向根節點，使其扁平化

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

union

如果 p 的根節點與 q 的根節點相同，就不做任何動作
如果不同，則將 q 的根節點的父節點設為 p 的根節點

1
2
3
4
void Union(int p, int q) {
    int a = find(p), b = find(q);
    if (a != b) return void(anc[a] = b);
}

初始化一維陣列

可以使用 iota() 來使陣列設定成每個節點的父節點都是自己（自己一組）

iota()：
可以為容器以遞增值為 1 的方式從初始值填充值
參數為（起始位置的迭代器, 結束位置的迭代器, 起始值）
當起始值為 -3 時，填充效果為：-3, -2, -1, 0, 1, 2 …

1
2
anc.resize(n);
iota(anc.begin(), anc.end(), 0);

範例

題目：UVA 10583

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> anc;

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

void Union(int p, int q) {
    int a = Find(p), b = Find(q);
    if (a != b) anc[a] = b;
}

signed main() {
    int n, m, c = 0;
    while (cin >> n >> m, n && m) {
        anc.resize(n);
        iota(anc.begin(), anc.end(), 0);

        while (m--) {
            int p, q;
            cin >> p >> q;
            Union(p-1, q-1);
        }

        unordered_set<int> s;
        for (auto i : anc) s.insert(Find(i));
        cout << "Case " << ++c << ": " << s.size() << '\n';

        anc.clear();
    }
}