DataStructure/union_find.hpp

• View this file on GitHub
• Last update: 2020-10-29 02:20:23+09:00
• Include: #include "DataStructure/union_find.hpp"

Verified with

• Verify/union_find.test.cpp

Code

#pragma once

#include <vector>

struct UnionFind {
    std::vector<int> par;
    int gnum;

    explicit UnionFind(int n) : par(n, -1), gnum(n) {}

    int find(int v) {
        return (par[v] < 0) ? v : (par[v] = find(par[v]));
    }

    void unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (par[u] > par[v]) std::swap(u, v);
        par[u] += par[v];
        par[v] = u;
        --gnum;
    }

    bool same(int u, int v) { return find(u) == find(v); }
    bool ispar(int v) { return par[v] < 0; }
    int size(int v) { return -par[find(v)]; }
};

#line 2 "DataStructure/union_find.hpp"

#include <vector>

struct UnionFind {
    std::vector<int> par;
    int gnum;

    explicit UnionFind(int n) : par(n, -1), gnum(n) {}

    int find(int v) {
        return (par[v] < 0) ? v : (par[v] = find(par[v]));
    }

    void unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (par[u] > par[v]) std::swap(u, v);
        par[u] += par[v];
        par[v] = u;
        --gnum;
    }

    bool same(int u, int v) { return find(u) == find(v); }
    bool ispar(int v) { return par[v] < 0; }
    int size(int v) { return -par[find(v)]; }
};

Back to top page