verify/LC-Unionfind.test.cpp

View this file on GitHub
Last update: 2025-05-30 20:02:37+09:00
Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

#include "../Library/DataStructure/UnionFind.hpp"

int main(){
    cin.tie(0)->sync_with_stdio(false);
    int N, Q; cin >> N >> Q;

    UnionFind uf(N);
    while(Q--){
        int t, u, v; cin >> t >> u >> v;
        if(t == 0) uf.Unite(u, v);
        else cout << uf.Same(u, v) << '\n';
    }
}

#line 1 "verify/LC-Unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

#line 2 "Library/DataStructure/UnionFind.hpp"

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 4 "Library/DataStructure/UnionFind.hpp"

class UnionFind{
    public:
    UnionFind(size_t n) : data_(n, -1){}

    int Find(const int k){
        if(data_[k] < 0) return k;
        int r = Find(data_[k]);
        return data_[k] = r;
    }

    bool Same(const int x, const int y){
        return Find(x) == Find(y);
    }

    bool Unite(int x, int y){
        x = Find(x), y = Find(y);
        if(x == y) return false;
        if(data_[x] > data_[y]) swap(x, y);
        data_[x] += data_[y];
        data_[y] = x;
        return true;
    }
    
    size_t Size(int k){
        int v = Find(k);
        return -data_[v];
    }

    vector<vector<int>> Group(){
        vector<vector<int>> ret(data_.size());
        for(int i = 0; i < data_.size(); ++i){
            ret[Find(i)].emplace_back(i);
        }
        ret.erase(remove_if(begin(ret), end(ret), [&](vector<int> &v){
            return v.empty();
        }), end(ret));
        return ret;
    }

    private:
    vector<int> data_;
};
#line 4 "verify/LC-Unionfind.test.cpp"

int main(){
    cin.tie(0)->sync_with_stdio(false);
    int N, Q; cin >> N >> Q;

    UnionFind uf(N);
    while(Q--){
        int t, u, v; cin >> t >> u >> v;
        if(t == 0) uf.Unite(u, v);
        else cout << uf.Same(u, v) << '\n';
    }
}