Union Find (data_structure/unionfind.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-04-27 17:12:50+09:00
• Include: #include "data_structure/unionfind.hpp"

互いに素な集合を管理します。

使い方

コンストラクタ

Unionfind(int n)

説明

n 個の要素を持つ Union-Find を構築します。最初は各要素がそれぞれ異なる集合に属しています。

• n: 要素数。

計算量

$O(N)$

merge

int merge(int a, int b)

説明

要素 a と要素 b が属する集合を併合します。a と b が既に同じ集合に属している場合は何も行いません。

• a: 要素のインデックス (0-indexed)。
• b: 要素のインデックス (0-indexed)。
• 戻り値: 併合後の集合の代表元のインデックス。

制約

$0 \le a < n$
$0 \le b < n$

計算量

$O(\alpha(N))$

bool same(int a, int b)

説明

要素 a と要素 b が同じ集合に属しているかを判定します。

• a: 要素のインデックス (0-indexed)。
• b: 要素のインデックス (0-indexed)。
• 戻り値: a と b が同じ集合に属していれば true、そうでなければ false。

制約

$0 \le a < n$
$0 \le b < n$

計算量

$O(\alpha(N))$

leader

int leader(int a)

説明

要素 a が属する集合の代表元を返します。

• a: 要素のインデックス (0-indexed)。
• 戻り値: 要素 a が属する集合の代表元のインデックス。

制約

$0 \le a < n$

計算量

$O(\alpha(N))$

size

int size(int a)

説明

要素 a が属する集合の要素数を返します。

• a: 要素のインデックス (0-indexed)。
• 戻り値: 要素 a が属する集合のサイズ。

制約

$0 \le a < n$

計算量

$O(\alpha(N))$

Required by

• misc/random.hpp

Verified with

• test/unionfind.test.cpp

Code

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

struct UnionFind {
    int n;
    std::vector<int> v;

    UnionFind() : n(0) {}
    explicit UnionFind(int n) : n(n), v(n, -1) {}

    int merge(int a, int b) {
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-v[x] < -v[y]) std::swap(x, y);
        v[x] += v[y];
        v[y] = x;
        return x;
    }

    bool same(int a, int b) {
        return leader(a) == leader(b);
    }

    int leader(int a) {
        if (v[a] < 0) return a;
        return leader(v[a]);
    }

    int size(int a) {
        return -v[leader(a)];
    }
};

#line 2 "data_structure/unionfind.hpp"
#include <algorithm>
#include <vector>

struct UnionFind {
    int n;
    std::vector<int> v;

    UnionFind() : n(0) {}
    explicit UnionFind(int n) : n(n), v(n, -1) {}

    int merge(int a, int b) {
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-v[x] < -v[y]) std::swap(x, y);
        v[x] += v[y];
        v[y] = x;
        return x;
    }

    bool same(int a, int b) {
        return leader(a) == leader(b);
    }

    int leader(int a) {
        if (v[a] < 0) return a;
        return leader(v[a]);
    }

    int size(int a) {
        return -v[leader(a)];
    }
};

Back to top page