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

• View this file on GitHub
• Last update: 2020-12-05 07:59:51+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

• Functional Graph(なもりグラフ)の分解 (graph/funtional-graph.hpp)
• graph/kruskal.hpp
• graph/minimum-cost-arborescence.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-2891.test.cpp
• verify/verify-aoj-other/aoj-2995.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.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 ... merge function
  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 ... merge function
  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