並查集的實現

思路

見並查集

程式碼

並查集

#include <iostream>
using namespace std;
int n, m;
const int MX = 1e6 + 1;
int parent[MX];
int setSize[MX];
int stk[MX];
void build() {
    for(int i = 0; i < n; i++) {
        parent[i] = i;
        setSize[i] = 1;
    }
}
int find(int x) {
    int cnt = 0; // 記錄沿途收集了幾個點
    while(x != parent[x]) { // 還沒有到根結點
        stk[cnt++] = x; // 記錄沿途節點
        x = parent[x]; // 往上跳
    }
    // 優化二：扁平化
    // 此時 x 在根結點
    // 將收集到的節點個 parent, 都指向根結點
    while(cnt > 0) {
        parent[stk[--cnt]] = x;
    }
    return x;
}
bool isSameSet(int x, int y) {
    return find(x) == find(y);
}
void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if(rootX != rootY) { // 根結點不同，需要合併
        // 優化一：小的合併到大的
        if(setSize[rootX] < setSize[rootY]) {
            parent[rootX] = rootY; 
            setSize[rootY] += setSize[rootX];
        }        
        else {
            parent[rootY] = rootX;
            setSize[rootX] += setSize[rootY];
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    int opt, x, y;
    build();
    for(int i = 0; i < m; i++) {
        cin >> opt >> x >> y;
        if(opt == 1) {
            cout << (isSameSet(x, y) ? "Yes" : "No") << "\n";
        }
        else {
            unite(x, y);
        }
    }
}

複雜度分析

• 時間複雜度：$O(m\alpha(n))$
• 空間複雜度：$O(n)$