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

View this file on GitHub
Last update: 2025-03-03 00:33:48+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 <cassert>
#include <vector>
using namespace std;

namespace asalib {
  namespace ds {
    class UnionFind {
      private:
      // par_size[i] < 0: size
      // par_size[i] >= 0: parent
      vector<int> par_size;
      size_t siz;

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

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

      int leader(size_t x) {
        assert(0 <= x && x < par_size.size());
        if (par_size[x] < 0) return x;
        return par_size[x] = leader(par_size[x]);
      }

      int size(size_t x) {
        assert(0 <= x && x < par_size.size());
        return -par_size[leader(x)];
      }

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

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

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

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

namespace asalib {
  namespace ds {
    class UnionFind {
      private:
      // par_size[i] < 0: size
      // par_size[i] >= 0: parent
      vector<int> par_size;
      size_t siz;

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

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

      int leader(size_t x) {
        assert(0 <= x && x < par_size.size());
        if (par_size[x] < 0) return x;
        return par_size[x] = leader(par_size[x]);
      }

      int size(size_t x) {
        assert(0 <= x && x < par_size.size());
        return -par_size[leader(x)];
      }

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

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

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