Union Find (Disjoint Set Union)
(library/data-structure/unionfind.hpp)

• View this file on GitHub
• Last update: 2026-03-10 00:09:38+09:00
• Include: #include "library/data-structure/unionfind.hpp"

Union Find (Disjoint Set Union)

グループ分けを管理するデータ構造。以下の操作をサポートする。

• merge(x, y): $x$ と $y$ が属するグループを併合する。 $O(\alpha(n))$
• same(x, y): $x$ と $y$ が同じグループに属するか判定する。 $O(\alpha(n))$
• leader(x): $x$ が属するグループの代表元を返す。 $O(\alpha(n))$
• size(x): $x$ が属するグループの大きさを返す。 $O(\alpha(n))$
• groups(): すべてのグループを列挙する。 $O(n)$
• count(): グループの数を返す。 $O(1)$

高速化のための工夫

Union by Size

merge(x, y) を呼ぶたびに、$x$ と $y$ が属するグループの大きさを比較し、小さい方を大きい方に併合する。 つまりマージテク。 $O(\log n)$ になる。

Path Compression

leader(x) を呼ぶたびに、$x$ から根に至る経路上の各要素の親を根に繋ぎ直す。 Union by Size と組み合わせることで、 $O(\alpha(n))$ になるらしい？

使い方

Test をみて

• Library Checker

Verified with

• tests/data-structure/unionfind/libchecker.test.cpp

Code

#pragma once

#include <algorithm>
#include <cassert>
#include <ranges>
#include <vector>
using namespace std;

namespace asalib::ds {
  class UnionFind {
    // par_size[i] < 0: size
    // par_size[i] >= 0: parent
    vector<int> par_size;
    int siz;
    constexpr int _leader(const int x) {
      // assert 済みな想定
      if (par_size[x] < 0) return x;
      return par_size[x] = _leader(par_size[x]);
    }

    public:
    UnionFind(): siz(0) {}
    constexpr explicit UnionFind(const int n) {
      siz = n;
      par_size.reserve(n);
      par_size.resize(n, -1);
    }

    constexpr void merge(int u, int v) {
      assert(u < ranges::ssize(par_size));
      assert(v < ranges::ssize(par_size));
      u = _leader(u), v = _leader(v);
      if (u == v) return;
      if (par_size[u] > par_size[v]) swap(u, v);
      // u is the larger group (-par_size[u] >= -par_size[v])
      par_size[u] += par_size[v];
      par_size[v] = u;
      --siz;
    }

    constexpr bool same(const int u, const int v) {
      assert(u < ranges::ssize(par_size));
      assert(v < ranges::ssize(par_size));
      return _leader(u) == _leader(v);
    }

    constexpr int leader(const int x) {
      assert(x < ranges::ssize(par_size));
      return _leader(x);
    }

    constexpr int size(const int x) {
      assert(x < ranges::ssize(par_size));
      return -par_size[_leader(x)];
    }

    constexpr vector<vector<int>> groups() {
      vector<vector<int>> res(par_size.size());
      for (int i = 0; i < ranges::ssize(par_size); ++i) res[_leader(i)].emplace_back(i);
      res.erase(ranges::remove_if(res, [](const vector<int>& v) {
                  return v.empty();
                }).begin(),
                res.end());
      return res;
    }

    constexpr int count() const { return siz; }
  };
}  // namespace asalib::ds

#line 2 "library/data-structure/unionfind.hpp"

#include <algorithm>
#include <cassert>
#include <ranges>
#include <vector>
using namespace std;

namespace asalib::ds {
  class UnionFind {
    // par_size[i] < 0: size
    // par_size[i] >= 0: parent
    vector<int> par_size;
    int siz;
    constexpr int _leader(const int x) {
      // assert 済みな想定
      if (par_size[x] < 0) return x;
      return par_size[x] = _leader(par_size[x]);
    }

    public:
    UnionFind(): siz(0) {}
    constexpr explicit UnionFind(const int n) {
      siz = n;
      par_size.reserve(n);
      par_size.resize(n, -1);
    }

    constexpr void merge(int u, int v) {
      assert(u < ranges::ssize(par_size));
      assert(v < ranges::ssize(par_size));
      u = _leader(u), v = _leader(v);
      if (u == v) return;
      if (par_size[u] > par_size[v]) swap(u, v);
      // u is the larger group (-par_size[u] >= -par_size[v])
      par_size[u] += par_size[v];
      par_size[v] = u;
      --siz;
    }

    constexpr bool same(const int u, const int v) {
      assert(u < ranges::ssize(par_size));
      assert(v < ranges::ssize(par_size));
      return _leader(u) == _leader(v);
    }

    constexpr int leader(const int x) {
      assert(x < ranges::ssize(par_size));
      return _leader(x);
    }

    constexpr int size(const int x) {
      assert(x < ranges::ssize(par_size));
      return -par_size[_leader(x)];
    }

    constexpr vector<vector<int>> groups() {
      vector<vector<int>> res(par_size.size());
      for (int i = 0; i < ranges::ssize(par_size); ++i) res[_leader(i)].emplace_back(i);
      res.erase(ranges::remove_if(res, [](const vector<int>& v) {
                  return v.empty();
                }).begin(),
                res.end());
      return res;
    }

    constexpr int count() const { return siz; }
  };
}  // namespace asalib::ds

Back to top page