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

View this file on GitHub
Last update: 2025-06-26 16:44:42+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 {
  namespace 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;
      uint _leader(uint x) {
        // assert 済みな想定
        if (par_size[x] < 0) return x;
        return par_size[x] = _leader(par_size[x]);
      }

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

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

      bool same(uint u, uint v) {
        assert(0 <= u && u < par_size.size());
        assert(0 <= v && v < par_size.size());
        return _leader(u) == _leader(v);
      }

      uint leader(uint x) {
        assert(0 <= x && x < par_size.size());
        return _leader(x);
      }

      uint size(uint x) {
        assert(0 <= x && x < par_size.size());
        return -par_size[_leader(x)];
      }

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

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

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

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

namespace asalib {
  namespace 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;
      uint _leader(uint x) {
        // assert 済みな想定
        if (par_size[x] < 0) return x;
        return par_size[x] = _leader(par_size[x]);
      }

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

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

      bool same(uint u, uint v) {
        assert(0 <= u && u < par_size.size());
        assert(0 <= v && v < par_size.size());
        return _leader(u) == _leader(v);
      }

      uint leader(uint x) {
        assert(0 <= x && x < par_size.size());
        return _leader(x);
      }

      uint size(uint x) {
        assert(0 <= x && x < par_size.size());
        return -par_size[_leader(x)];
      }

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

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

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