cpp_src/data_structure/DisjointSetUnion.hpp

View this file on GitHub
Last update: 2022-04-10 12:39:22+09:00
Include: #include "cpp_src/data_structure/DisjointSetUnion.hpp"

Verified with

Code

class unionfind {
    vector<int> par, rank;

   public:
    void init(int n) {
        par.resize(n);
        rank.resize(n);

        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    unionfind() {}
    unionfind(int n) { init(n); }

    int find(int x) {
        if (par[x] == x)
            return x;
        else
            return par[x] = find(par[x]);
    }

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;

        if (rank[x] < rank[y])
            par[x] = y;
        else {
            par[y] = x;
            if (rank[x] == rank[y]) ++rank[x];
        }
        return true;
    }

    bool same(int x, int y) { return (find(x) == find(y)); }
};

#line 1 "cpp_src/data_structure/DisjointSetUnion.hpp"
class unionfind {
    vector<int> par, rank;

   public:
    void init(int n) {
        par.resize(n);
        rank.resize(n);

        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    unionfind() {}
    unionfind(int n) { init(n); }

    int find(int x) {
        if (par[x] == x)
            return x;
        else
            return par[x] = find(par[x]);
    }

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;

        if (rank[x] < rank[y])
            par[x] = y;
        else {
            par[y] = x;
            if (rank[x] == rank[y]) ++rank[x];
        }
        return true;
    }

    bool same(int x, int y) { return (find(x) == find(y)); }
};