verify/ds/dsu.test.cpp

• View this file on GitHub
• Last update: 2024-12-10 21:37:51-05:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• algo/common.h
• algo/ds/dsu.h

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include "algo/common.h"

/* #include */
#include "algo/ds/dsu.h"

using namespace std;
using namespace algo;
using ds::dsu;

void solve() {
    int n, q;
    cin >> n >> q;
    dsu dsu(n);
    for (int i = 0; i < q; i++) {
        int t, u, v;
        cin >> t >> u >> v;
        if (t == 0)
            dsu.unite(u, v);
        else
            cout << (dsu.is_same(u, v) ? 1 : 0) << '\n';
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    // int t;
    // cin >> t;
    // while (t--)
    solve();
}

#line 1 "verify/ds/dsu.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#line 2 "algo/common.h"
#ifndef PREPROCESS
#include <bits/stdc++.h>
#endif

namespace algo {}

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#line 3 "verify/ds/dsu.test.cpp"

/* #include */
#line 3 "algo/ds/dsu.h"

namespace algo::ds {

template <bool union_by_size = true, bool path_compression = true>
struct dsu {
    dsu(int n) : e(std::vector<int>(n, -1)) {
    }
    int get(int x) {
        if (e[x] < 0) return x;
        if (path_compression) return e[x] = get(e[x]);
        return get(e[x]);
    }
    bool is_same(int a, int b) {
        return get(a) == get(b);
    }
    int size(int x) {
        return -e[get(x)];
    }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        if (union_by_size && e[x] > e[y]) std::swap(x, y);
        e[x] += e[y];
        e[y] = x;
        return true;
    }
    friend std::ostream &operator<<(std::ostream &os, dsu s) {
        os << "[";
        bool first = true;
        for (int i = 0; i < sz(s.e); i++) {
            if (s.get(i) == i) {
                if (!first) os << ", ";
                first = false;
                os << "[" << i;
                for (int j = 0; j < sz(s.e); j++) {
                    if (j != i && s.get(j) == i) {
                        os << ", " << j;
                    }
                }
                os << "]";
            }
        }
        return os << "]";
    }

private:
    std::vector<int> e;
};

} // namespace algo::ds
#line 6 "verify/ds/dsu.test.cpp"

using namespace std;
using namespace algo;
using ds::dsu;

void solve() {
    int n, q;
    cin >> n >> q;
    dsu dsu(n);
    for (int i = 0; i < q; i++) {
        int t, u, v;
        cin >> t >> u >> v;
        if (t == 0)
            dsu.unite(u, v);
        else
            cout << (dsu.is_same(u, v) ? 1 : 0) << '\n';
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    // int t;
    // cin >> t;
    // while (t--)
    solve();
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	6 ms	3 MB
g++	max_random_00	AC	38 ms	4 MB
g++	max_random_01	AC	40 ms	4 MB
g++	max_random_02	AC	36 ms	4 MB
g++	path_00	AC	33 ms	4 MB
g++	path_01	AC	33 ms	4 MB
g++	path_02	AC	31 ms	4 MB
g++	path_03	AC	31 ms	4 MB
g++	random_00	AC	30 ms	4 MB
g++	random_01	AC	30 ms	4 MB
g++	random_02	AC	24 ms	4 MB
g++	random_03	AC	10 ms	4 MB
g++	random_04	AC	20 ms	4 MB
g++	random_05	AC	27 ms	4 MB
g++	random_06	AC	23 ms	4 MB
g++	random_07	AC	7 ms	4 MB
g++	random_08	AC	12 ms	4 MB
g++	random_09	AC	36 ms	4 MB

Back to top page