Union Find (Disjoint Set Union)
(src/datastructure/UnionFind.hpp)

• View this file on GitHub
• Last update: 2023-01-12 22:28:24+09:00
• Include: #include "src/datastructure/UnionFind.hpp"

概要

各集合をその集合内の代表元によって特徴づけることで素集合を扱うデータ構造． 主に頂点 $x, y$ の属する集合のマージやそれらが同一の集合に属しているかの判定を均し $O(\alpha(n))$ で行うことができる． ここで，$\alpha(n)$ は Ackermann 関数 $A(n, n)$ の逆関数である．

メンバ関数	効果	時間計算量
UnionFind(n)	要素数 $n$ で初期化する．	$O(n)$
find(x)	頂点 $x$ の属する集合の代表元を返す．	均し $O(\alpha(n))$
merge(x, y)	頂点 $x, y$ が属する集合を併合する．	均し $O(\alpha(n))$
same(x, y)	頂点 $x, y$ が同一の集合に属するか判定する．	均し $O(\alpha(n))$
size(x)	頂点 $x$ が属する集合の要素数を返す．	均し $O(\alpha(n))$
count()	素集合の数を返す．	$O(1)$
groups()	頂点を連結性で分割した同値類の情報を返す．	$O(n)$
operator[x]	頂点 $x$ の属する集合の代表元を返す．	均し $O(\alpha(n))$

Verified with

• test/yosupo/unionfind.test.cpp

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <vector>

struct UnionFind {
    UnionFind(int n) : n(n), num(n), data(n, -1) {}

    int find(int x) {
        assert(0 <= x && x < n);
        return data[x] < 0 ? x : data[x] = find(data[x]);
    }

    bool merge(int x, int y) {
        assert(0 <= x && x < n);
        assert(0 <= y && y < n);
        if ((x = find(x)) == (y = find(y))) return false;
        if (-data[x] < -data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
        num--;
        return true;
    }

    bool same(int x, int y) {
        assert(0 <= x && x < n);
        assert(0 <= y && y < n);
        return find(x) == find(y);
    }

    int size(int x) {
        assert(0 <= x && x < n);
        return -data[find(x)];
    }

    int count() const { return num; }

    std::vector<std::vector<int>> groups() {
        std::vector<std::vector<int>> res(n);
        for (int i = 0; i < n; i++) res[find(i)].emplace_back(i);
        res.erase(std::remove_if(res.begin(), res.end(), [&](const std::vector<int>& v) { return v.empty(); }));
        return res;
    }

    int operator[](int x) { return find(x); }

private:
    int n, num;
    // root node : -1 * component size
    // otherwise : parent
    std::vector<int> data;
};

#line 2 "src/datastructure/UnionFind.hpp"
#include <algorithm>
#include <cassert>
#include <vector>

struct UnionFind {
    UnionFind(int n) : n(n), num(n), data(n, -1) {}

    int find(int x) {
        assert(0 <= x && x < n);
        return data[x] < 0 ? x : data[x] = find(data[x]);
    }

    bool merge(int x, int y) {
        assert(0 <= x && x < n);
        assert(0 <= y && y < n);
        if ((x = find(x)) == (y = find(y))) return false;
        if (-data[x] < -data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
        num--;
        return true;
    }

    bool same(int x, int y) {
        assert(0 <= x && x < n);
        assert(0 <= y && y < n);
        return find(x) == find(y);
    }

    int size(int x) {
        assert(0 <= x && x < n);
        return -data[find(x)];
    }

    int count() const { return num; }

    std::vector<std::vector<int>> groups() {
        std::vector<std::vector<int>> res(n);
        for (int i = 0; i < n; i++) res[find(i)].emplace_back(i);
        res.erase(std::remove_if(res.begin(), res.end(), [&](const std::vector<int>& v) { return v.empty(); }));
        return res;
    }

    int operator[](int x) { return find(x); }

private:
    int n, num;
    // root node : -1 * component size
    // otherwise : parent
    std::vector<int> data;
};

Back to top page