Union-Find
(structure/union_find.cpp)

• View this file on GitHub
• Last update: 2022-01-28 02:17:51+09:00

経路圧縮とサイズ比較をどちらも行っているため、クエリあたりの計算量は $O(\alpha(N))$ になっているはず。

• find(x): $x$ が属する集合の代表元を返す
• same(x, y): $x$ と $y$ が同じ集合に属するかどうかの bool 値を返す
• size(x): $x$ が属する集合の濃度 (要素数) を返す
• size(): 素集合がいくつ存在するかを返す
• unite(x, y): $x$ と $y$ が同じ集合に属するなら false を返す。そうでなければ true を返すとともに、$x$ が属する集合と $y$ が属する集合を併合する

Verified with

• verifying_test/AOJ/DSL_1_A/union_find.test.cpp
• verifying_test/yosupo/data_structure/unionfind/union_find.test.cpp

Code

#pragma once

/**
 * @brief Union-Find
 * @docs docs/structure/union_find.md
 */

#include <algorithm>
#include <vector>

struct UnionFind {
private:
    const int n;
    int size_;
    vector<int> uf;
public:
    // 初期化 UnionFind uni(n) のように宣言すれば良い

    UnionFind(int _n) : n(_n), size_(_n), uf(_n, -1) {}
    void reset() {
        size_ = n;
        fill(uf.begin(), uf.end(), -1);
    }
    // find (木の根を求める)

    int find(int x) {return (uf[x] < 0) ? x : uf[x] = find(uf[x]);}
    // x と y が同じ集合に属するかどうか

    bool same(int x, int y) {return find(x) == find(y);}
    // x が属する集合の要素数

    int size(int x) {return -uf[find(x)];}
    // 集合はいくつあるか

    int size()      {return size_;}
    // x と y の属する集合を併合

    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if(x == y) return false;
        size_--;
        if(-uf[x] < -uf[y]) swap(x, y);
        uf[x] += uf[y]; uf[y] = x;
        return true;
    }
};

#line 2 "structure/union_find.cpp"

/**
 * @brief Union-Find
 * @docs docs/structure/union_find.md
 */

#include <algorithm>
#include <vector>

struct UnionFind {
private:
    const int n;
    int size_;
    vector<int> uf;
public:
    // 初期化 UnionFind uni(n) のように宣言すれば良い

    UnionFind(int _n) : n(_n), size_(_n), uf(_n, -1) {}
    void reset() {
        size_ = n;
        fill(uf.begin(), uf.end(), -1);
    }
    // find (木の根を求める)

    int find(int x) {return (uf[x] < 0) ? x : uf[x] = find(uf[x]);}
    // x と y が同じ集合に属するかどうか

    bool same(int x, int y) {return find(x) == find(y);}
    // x が属する集合の要素数

    int size(int x) {return -uf[find(x)];}
    // 集合はいくつあるか

    int size()      {return size_;}
    // x と y の属する集合を併合

    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if(x == y) return false;
        size_--;
        if(-uf[x] < -uf[y]) swap(x, y);
        uf[x] += uf[y]; uf[y] = x;
        return true;
    }
};

Back to top page