UnionFind木のサンプルコードと問題(https://atcoder.jp/contests/abc097/tasks/arc097_b , https://atcoder.jp/contests/atc001/tasks/unionfind_a )の解答例

abc097-D.cpp

#include <iostream>
#include <vector>
using namespace std;

struct UnionFind
{
    vector<int> parent;
    UnionFind(int n) : parent(n) {
        for(int i = 0; i < n; i++) parent[i] = i;
    }

    int root(int x){
        return x == parent[x] ? x : (parent[x] = root(parent[x])); // 経路圧縮
    }

    void unite(int x, int y){
        int rx = root(x), ry = root(y);
        if(rx != ry) parent[rx] = parent[ry];
        return;
    }

    bool isSame(int x, int y){
        return root(x) == root(y);
    }
};


int main()
{
    int n, m, xi, yi, ans = 0;
    cin >> n >> m;
    vector<int> p(n);
    for(int i = 0; i < n; i++){
        cin >> p[i];
        p[i]--;
    }

    UnionFind u(n);
    for(int i = 0; i < m; i++){
        cin >> xi >> yi;
        u.unite(xi - 1, yi - 1);
    }
    for(int i = 0; i < n; i++){
        if(u.isSame(i, p[i])) ans++;
    }
    cout << ans << endl;
    return 0;
}

atc001-B.cpp

#include <iostream>
#include <vector>
using namespace std;

struct UnionFind
{
    vector<int> parent;
    UnionFind(int n) : parent(n) {
        for(int i = 0; i < n; i++) parent[i] = i;
    }

    int root(int x){
        return x == parent[x] ? x : (parent[x] = root(parent[x])); // 経路圧縮
    }

    void unite(int x, int y){
        int rx = root(x), ry = root(y);
        if(rx != ry) parent[rx] = parent[ry];
        return;
    }

    bool isSame(int x, int y){
        return root(x) == root(y);
    }
};


int main()
{
    int n, q, pi, ai, bi;
    cin >> n >> q;
    UnionFind tree(n);
    vector<string> ans;

    for(int i = 0; i < q; i++){
        cin >> pi >> ai >> bi;
        if(!pi) tree.unite(ai, bi);
        else ans.push_back(tree.isSame(ai, bi) ? "Yes" : "No");
    }
    for(auto iter = ans.begin(); iter != ans.end(); iter++)
    {
        cout << *iter << endl;
    }
    return 0;
}

UnionFind.cpp

struct UnionFind
{
    vector<int> parent;
    UnionFind(int n) : parent(n) {
        for(int i = 0; i < n; i++) parent[i] = i;
    }

    int root(int x){
        return x == parent[x] ? x : (parent[x] = root(parent[x]));
    }

    void unite(int x, int y){
        int rx = root(x), ry = root(y);
        if(rx != ry) parent[rx] = parent[ry];
        return;
    }

    bool isSame(int x, int y){
        return root(x) == root(y);
    }
};