UnionFind 素集合データ構造
(library/various/union_find.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/various/union_find.hpp"

UnionFind 素集合データ構造

できること

• 集合をつなげたり。切れはしない

計算量

• 構築: $O(N)$
• 自分のグループサイズuf[p]: $O(α(N))$
• 自分の親を見つけるfind: $O(α(N))$
• 同じグループにするunite: $O(α(N))$

使い方

UnionFind uf(N);
int sz = uf[p];
if (uf.unite(a, b)) {
    // つなげた場合
}
if (uf.find(a) == uf.find(b)) {
    // 同じグループである
}

Required by

• Kruskal (library/graph/mst/kruskal.hpp)

Verified with

• 最小全域木 - クラスカルのテスト (tests/graph.mst.kruskal.test.cpp)
• 木 - 木の同型性判定のテスト (tests/graph.tree.tree_isomorphism.test.cpp)
• Union Findのテスト (tests/various.union_find.test.cpp)

Code

#pragma once
struct UnionFind {
  private:
    vector<int> parent, size;

  public:
    UnionFind(int N) {
        parent.assign(N, -1);
        size.assign(N, 1);
    }
    int operator[](int p) { return size[find(p)]; }
    int find(int p) { return !~parent[p] ? p : (parent[p] = find(parent[p])); }
    bool unite(int a, int b) {
        int x = find(a), y = find(b);
        if (x == y) return false;
        if (size[x] > size[y]) swap(x, y);
        parent[x] = y, size[y] += size[x];
        return true;
    }
};

#line 2 "library/various/union_find.hpp"
struct UnionFind {
  private:
    vector<int> parent, size;

  public:
    UnionFind(int N) {
        parent.assign(N, -1);
        size.assign(N, 1);
    }
    int operator[](int p) { return size[find(p)]; }
    int find(int p) { return !~parent[p] ? p : (parent[p] = find(parent[p])); }
    bool unite(int a, int b) {
        int x = find(a), y = find(b);
        if (x == y) return false;
        if (size[x] > size[y]) swap(x, y);
        parent[x] = y, size[y] += size[x];
        return true;
    }
};

Back to top page