P3367 並查集

思路

同並查集的實現，只需稍微修改輸入輸出，
這個版本相比起來較為簡潔。

程式碼

並查集

#include <iostream>
#include <numeric>
using namespace std;
int n, m;
const int MX = 2e5 + 1;
int parent[MX];
int find(int x) {
    // 遞迴版本的扁平化
    if(x != parent[x]) { // 自己的 paernt 不是自己, 表示可以繼續往上找
        // find(parent[x]) 是往上找到的根結點 root 
        // 把自己的指向改成 root
        parent[x] = find(parent[x]);
    }
    return parent[x]; // 現在 parent[x] 是 root
}
bool isSameSet(int x, int y) {
    return find(x) == find(y);
}
void unite(int x, int y) {
    parent[find(x)] = find(y);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    iota(parent, parent + n, 0); // 相當於 build 函數
    int z, x, y;
    for(int i = 0; i < m; i++) {
        cin >> z >> x >> y;
        if(z == 2) cout << (isSameSet(x, y) ? "Y" : "N") << "\n";
        else unite(x, y);
    }
}

複雜度分析

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