DataStructure/test/aizu_dsl_1_a_dsu.test.cpp

View this file on GitHub
Last update: 2023-01-07 01:46:12+08:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A

Depends on

DataStructure/DSU/DisjointSet.h

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A"

#include <bits/stdc++.h>
using namespace std;

#include "../DSU/DisjointSet.h"

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
    DSU dsu(n);
    while (q--) {
        int typ, x, y; cin >> typ >> x >> y;
        if (typ == 0) dsu.merge(x, y);
        else cout << dsu.same_component(x, y) << '\n';
    }
}

#line 1 "DataStructure/test/aizu_dsl_1_a_dsu.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A"

#include <bits/stdc++.h>
using namespace std;

#line 1 "DataStructure/DSU/DisjointSet.h"
// DisjointSet {{{
struct DSU {
    vector<int> lab;

    DSU(int n) : lab(n+1, -1) {}

    int getRoot(int u) {
        if (lab[u] < 0) return u;
        return lab[u] = getRoot(lab[u]);
    }

    bool merge(int u, int v) {
        u = getRoot(u); v = getRoot(v);
        if (u == v) return false;
        if (lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        return true;
    }

    bool same_component(int u, int v) {
        return getRoot(u) == getRoot(v);
    }

    int component_size(int u) {
        return -lab[getRoot(u)];
    }
};
// }}}
#line 7 "DataStructure/test/aizu_dsl_1_a_dsu.test.cpp"

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
    DSU dsu(n);
    while (q--) {
        int typ, x, y; cin >> typ >> x >> y;
        if (typ == 0) dsu.merge(x, y);
        else cout << dsu.same_component(x, y) << '\n';
    }
}