Unionfind
(unionfind/unionfind.hpp)

• View this file on GitHub
• Last update: 2025-12-10 04:21:17+09:00
• Include: #include "unionfind/unionfind.hpp"

無向グラフに対して

• 辺の追加
• $2$ 頂点が連結かの判定

をならし $O(\alpha(n))$ 時間で処理することが出来ます。

コンストラクタ

Unionfind uf(int n)

$n$ 頂点 $0$ 辺の無向グラフを作ります。

計算量

• $O(n)$

merge

int uf.merge(int x, int y)

辺 $(x, y)$ を足します。

$x, y$ が連結だった場合はその代表元を、$x, y$ が非連結だった場合は新たな代表元を返します。 すなわち、辺の追加により連結成分がマージされる時、新たな代表元は元の連結成分の代表元のうちどちらかになります。

制約

• $0 \leq x < n$
• $0 \leq y < n$

計算量

• ならし $O(\alpha(n))$

same

bool uf.same(int x, int y)

頂点 $x, y$ が連結かどうかを返します。

制約

• $0 \leq x < n$
• $0 \leq y < n$

計算量

• ならし $O(\alpha(n))$

leader

int uf.leader(int x)

頂点 $x$ の属する連結成分の代表元を返します。

制約

• $0 \leq x < n$

計算量

• ならし $O(\alpha(n))$

size

int uf.size(int x)

頂点 $x$ の属する連結成分のサイズを返します。

制約

• $0 \leq x < n$

計算量

• ならし $O(\alpha(n))$

groups

std::vector<std::vector<int>> uf.groups()

グラフを連結成分に分け、その情報を返します。

返り値は「「一つの連結成分の頂点番号のリスト」のリスト」です。 （内側外側限らず）std::vector 内でどの順番で格納されているかは未定義です。

計算量

• $O(n)$

Required by

• Kruskal's algorithm (クラスカル法) (graph/kruskal.hpp)
• Minimum Steiner Tree (最小シュタイナー木) (graph/minimum_steiner_tree.hpp)

Verified with

• unionfind/test/unionfind.test.cpp
• unionfind/test/unionfind_groups.test.cpp
• verify/graph/kruskal.test.cpp
• verify/graph/minimum_steiner_tree.test.cpp

Code

#pragma once

#include <algorithm>
#include <cassert>
#include <vector>

// Unionfind
struct Unionfind {
    int n;
    std::vector<int> parent;

    Unionfind() = default;

    explicit Unionfind(int n) : n(n), parent(n, -1) {}

    int leader(int x) {
        assert(0 <= x and x < n);
        if (parent[x] < 0) {
            return x;
        } else {
            return parent[x] = leader(parent[x]);
        }
    }

    int merge(int x, int y) {
        assert(0 <= x and x < n);
        assert(0 <= y and y < n);
        x = leader(x);
        y = leader(y);
        if (x == y) {
            return x;
        }
        if (-parent[x] < -parent[y]) {
            std::swap(x, y);
        }
        parent[x] += parent[y];
        parent[y] = x;
        return x;
    }

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

    int size(int x) {
        assert(0 <= x and x < n);
        return -parent[leader(x)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(n), group_size(n);
        for (int i = 0; i < n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(n);
        for (int i = 0; i < n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(std::remove_if(
                         result.begin(), result.end(),
                         [&](const std::vector<int>& v) { return v.empty(); }),
                     result.end());
        return result;
    }
};

#line 2 "unionfind/unionfind.hpp"

#include <algorithm>
#include <cassert>
#include <vector>

// Unionfind
struct Unionfind {
    int n;
    std::vector<int> parent;

    Unionfind() = default;

    explicit Unionfind(int n) : n(n), parent(n, -1) {}

    int leader(int x) {
        assert(0 <= x and x < n);
        if (parent[x] < 0) {
            return x;
        } else {
            return parent[x] = leader(parent[x]);
        }
    }

    int merge(int x, int y) {
        assert(0 <= x and x < n);
        assert(0 <= y and y < n);
        x = leader(x);
        y = leader(y);
        if (x == y) {
            return x;
        }
        if (-parent[x] < -parent[y]) {
            std::swap(x, y);
        }
        parent[x] += parent[y];
        parent[y] = x;
        return x;
    }

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

    int size(int x) {
        assert(0 <= x and x < n);
        return -parent[leader(x)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(n), group_size(n);
        for (int i = 0; i < n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(n);
        for (int i = 0; i < n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(std::remove_if(
                         result.begin(), result.end(),
                         [&](const std::vector<int>& v) { return v.empty(); }),
                     result.end());
        return result;
    }
};

Back to top page