Union Find(Disjoint Set Union)
(data-structure/union-find.hpp)

• View this file on GitHub
• Last update: 2024-08-10 13:03:16+09:00
• Include: #include "data-structure/union-find.hpp"

Union-Find Tree(Disjoint Set Union)

概要

Union-Find Treeとは、素集合データ構造に対して

• 頂点$x,y$が属している二つの集合をマージする
• 頂点$x,y$が同じ集合に属しているかを判定する

という二つの操作をともに$\mathrm{O}(\alpha(n))$で高速に実行するライブラリである。($\alpha(n)$はアッカーマン関数$A(n, n)$の逆関数)

使い方

• UnionFind(int sz)：サイズ$sz$のUnionFindを生成する。計算量$\mathrm{O}(1)$
• unite(int x, int y)：xとyをマージする。返り値はマージに成功したらtrue、失敗したらfalseを返す。計算量$\mathrm{O}(\alpha(n))$($n$はUnionFindのサイズ)
• find(int k)：kの根を返す。計算量$\mathrm{O}(\alpha(n))$
• same(int x, int y)：xとyが同じ連結成分に所属しているかを返す。計算量$\mathrm{O}(\alpha(n))$
• size(int k)：xを含む連結成分のサイズを返す。

Required by

• graph/functional-graph.hpp
• graph/kruskal.hpp
• graph/minimum-cost-arborescence.hpp
• Functional Graph(なもりグラフ)の分解 (graph/namori.hpp)

Verified with

• verify/verify-aoj-dsl/aoj-dsl-1-a.test.cpp
• verify/verify-aoj-grl/aoj-grl-2-a.test.cpp
• verify/verify-aoj-other/aoj-2821.test.cpp
• verify/verify-aoj-other/aoj-2891-2.test.cpp
• verify/verify-aoj-other/aoj-2891.test.cpp
• verify/verify-aoj-other/aoj-2995.test.cpp
• verify/verify-unit-test/parallel-union-find.test.cpp
• verify/verify-unit-test/tree-path.test.cpp
• verify/verify-yosupo-graph/yosupo-directed-mst.test.cpp
• verify/verify-yuki/yuki-1170-divide-interval.test.cpp
• verify/verify-yuki/yuki-1254-2.test.cpp
• verify/verify-yuki/yuki-1254.test.cpp
• verify/verify-yuki/yuki-1303.test.cpp
• verify/verify-yuki/yuki-2588.test.cpp

Code

#pragma once

struct UnionFind {
  vector<int> data;
  UnionFind(int N) : data(N, -1) {}

  int find(int k) { return data[k] < 0 ? k : data[k] = find(data[k]); }

  int unite(int x, int y) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }

  // f(x, y) : x に y をマージ
  template<typename F>
  int unite(int x, int y,const F &f) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    f(x, y);
    return true;
  }

  int size(int k) { return -data[find(k)]; }

  int same(int x, int y) { return find(x) == find(y); }
};

/**
 * @brief Union Find(Disjoint Set Union)
 * @docs docs/data-structure/union-find.md
 */

#line 2 "data-structure/union-find.hpp"

struct UnionFind {
  vector<int> data;
  UnionFind(int N) : data(N, -1) {}

  int find(int k) { return data[k] < 0 ? k : data[k] = find(data[k]); }

  int unite(int x, int y) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }

  // f(x, y) : x に y をマージ
  template<typename F>
  int unite(int x, int y,const F &f) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    f(x, y);
    return true;
  }

  int size(int k) { return -data[find(k)]; }

  int same(int x, int y) { return find(x) == find(y); }
};

/**
 * @brief Union Find(Disjoint Set Union)
 * @docs docs/data-structure/union-find.md
 */

Back to top page