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

• View this file on GitHub
• Last update: 2025-08-17 00:21:01+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 <vector>
using namespace std;

namespace asalib::ds {
  class UnionFind {
    private:
    using uint = unsigned int;

    // par_size[i] < 0: size
    // par_size[i] >= 0: parent
    // どうせ 32bit に収まる範囲でしか使わないので int, uint にする
    vector<int> par_size;
    uint siz;
    constexpr uint _leader(const uint 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 uint n) {
      siz = n;
      par_size.reserve(n);
      par_size.resize(n, -1);
    }

    constexpr void merge(uint u, uint v) {
      assert(u < par_size.size());
      assert(v < par_size.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 uint u, const uint v) {
      assert(u < par_size.size());
      assert(v < par_size.size());
      return _leader(u) == _leader(v);
    }

    constexpr uint leader(const uint x) {
      assert(x < par_size.size());
      return _leader(x);
    }

    constexpr uint size(const uint x) {
      assert(x < par_size.size());
      return -par_size[_leader(x)];
    }

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

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

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

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

namespace asalib::ds {
  class UnionFind {
    private:
    using uint = unsigned int;

    // par_size[i] < 0: size
    // par_size[i] >= 0: parent
    // どうせ 32bit に収まる範囲でしか使わないので int, uint にする
    vector<int> par_size;
    uint siz;
    constexpr uint _leader(const uint 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 uint n) {
      siz = n;
      par_size.reserve(n);
      par_size.resize(n, -1);
    }

    constexpr void merge(uint u, uint v) {
      assert(u < par_size.size());
      assert(v < par_size.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 uint u, const uint v) {
      assert(u < par_size.size());
      assert(v < par_size.size());
      return _leader(u) == _leader(v);
    }

    constexpr uint leader(const uint x) {
      assert(x < par_size.size());
      return _leader(x);
    }

    constexpr uint size(const uint x) {
      assert(x < par_size.size());
      return -par_size[_leader(x)];
    }

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

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

Back to top page