library/test/yosupo/unionfind.test.cpp

• View this file on GitHub
• Last update: 2024-03-25 12:22:53+06:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• DSU (library/ds/dsu.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include <bits/stdc++.h>
using namespace std;
#include "../../ds/dsu.hpp"

int main() {
    ios::sync_with_stdio(0);
    int n, q, typ, u, v;
    cin>>n>>q;
    DSU dsu(n);
    while(q--) {
        cin>>typ>>u>>v;
        if(typ) {
            cout<<dsu.connected(u, v)<<endl;
        } else {
            dsu.unite(u, v);
        }
    }
    return 0;
}

#line 1 "library/test/yosupo/unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include <bits/stdc++.h>
using namespace std;
#line 1 "library/ds/dsu.hpp"
struct DSU {
    vector<int> par;
    int cc; // connected components
    DSU(int n) : par(n, -1), cc(n) {}
    // get representive component (uses path compression)
    int get(int x) { return par[x] < 0 ? x : par[x] = get(par[x]); }
    // check whether a and b are in the same connected component
    bool connected(int a, int b) { return get(a) == get(b); }
    int size(int x) { return -par[get(x)]; }
    int groups() { return cc; } // number of groups
    int leader(int v) const {
        while (par[v] > -1)
            v = par[v];
        return v;
    }
    bool unite(int x, int y) { // union by size
        x = get(x), y = get(y);
        if (x == y)
            return false;
        cc--;
        if (par[x] > par[y])
            swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
};
#line 5 "library/test/yosupo/unionfind.test.cpp"

int main() {
    ios::sync_with_stdio(0);
    int n, q, typ, u, v;
    cin>>n>>q;
    DSU dsu(n);
    while(q--) {
        cin>>typ>>u>>v;
        if(typ) {
            cout<<dsu.connected(u, v)<<endl;
        } else {
            dsu.unite(u, v);
        }
    }
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	7 ms	4 MB
g++	path_00	AC	123 ms	4 MB
g++	path_01	AC	101 ms	4 MB
g++	path_02	AC	37 ms	4 MB
g++	path_03	AC	36 ms	4 MB
g++	random_00	AC	103 ms	4 MB
g++	random_01	AC	110 ms	4 MB
g++	random_02	AC	86 ms	4 MB
g++	random_03	AC	24 ms	4 MB
g++	random_04	AC	71 ms	4 MB
g++	random_05	AC	98 ms	4 MB
g++	random_06	AC	80 ms	4 MB
g++	random_07	AC	14 ms	4 MB
g++	random_08	AC	39 ms	4 MB
g++	random_09	AC	136 ms	4 MB

Back to top page