verify/Datastructure_dsu.test.cpp

View this file on GitHub
Last update: 2025-01-10 00:00:54+09:00
Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include "../Utility/template.hpp"
#include "../Datastructure/dsu.hpp"

int main() {
    int N, Q;
    cin >> N >> Q;
    dsu d(N);
    while(Q--) {
        int t, u, v;
        cin >> t >> u >> v;
        if(t==0) {
            d.merge(u, v);
        }
        else {
            if(d.same(u, v)) cout << 1 << '\n';
            else cout << 0 << '\n';
        }

    }
}

#line 1 "verify/Datastructure_dsu.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/dsu.hpp"
struct dsu {
    using vi = vector<int>;   
    using vvi = vector<vector<int>>;
    vi par, sz, es;
    int cc;

    dsu(int n) {
        par = vi(n);
        sz = vi(n, 1);
        es = vi(n, 0);
        cc = n;
        iota(all(par), 0);
    }
  
    int leader(int u) {
        if (par[u] != u) {
            return par[u] = leader(par[u]);
        }    
         return u;
    }
    
    bool same(int a, int b) {
        return leader(a) == leader(b);
    }
    
    bool merge(int a, int b) {
        a = leader(a), b = leader(b);
        if(sz[a] < sz[b]) swap(a, b);

        if(a == b) {
            ++es[a];
            return false;
        }
        else {
            cc--;
            par[b] = leader(a);
            sz[a] += sz[b];
            es[a] += es[b] + 1;
            return true;
        }
    }

    //以下、必要な物を書く

    int size(int u) {
        return sz[leader(u)];
    }

    
    int componentcnt() {
        return cc;
    }
    
    int edgecnt(int u) {
        return es[leader(u)];
    }

    vvi groups() {
        int n = par.size();
        vvi ms(n);
        rep(v, 0, n) {
            ms[leader(v)].push_back(v);
        }

        vvi res;
        rep(i, 0, n) if(ms[i].size() > 0) {
            res.push_back(ms[i]);
        }

        return res;
    }

};

/*
@brief dsu
@docs doc/dsu.md
*/
#line 4 "verify/Datastructure_dsu.test.cpp"

int main() {
    int N, Q;
    cin >> N >> Q;
    dsu d(N);
    while(Q--) {
        int t, u, v;
        cin >> t >> u >> v;
        if(t==0) {
            d.merge(u, v);
        }
        else {
            if(d.same(u, v)) cout << 1 << '\n';
            else cout << 0 << '\n';
        }

    }
}