Union-Find (src/DataStructure/UnionFind.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2024-09-20 12:04:43+09:00
Include: #include "src/DataStructure/UnionFind.hpp"

`UnionFind` クラス

いわゆる普通の Union-Find．
以下，$\alpha(n)$ はアッカーマン関数の逆関数であり，計算量はならしである

メンバ関数	概要	計算量
`UnionFind(n)`	コンストラクタ. 要素数 $n$ を渡す.
`size(u)`	要素 $u$ の属する集合のサイズを返す.
`leader(u)`	要素 $u$ の属する集合の代表元を返す.	$O(\alpha(n))$
`connected(u,v)`	要素 $u,v$ が同じ集合に属していれば `true` を返す．	$O(\alpha(n))$
`unite(u,v)`	要素 $u,v$ それぞれが属する集合を併合する．すでに要素 $u,v$ が同じ集合に属していれば，`false` を返す．	$O(\alpha(n))$

Required by

Verified with

Code

#pragma once
#include <vector>
#include <algorithm>
class UnionFind {
 std::vector<int> par;
public:
 UnionFind(int n): par(n, -1) {}
 int leader(int u) { return par[u] < 0 ? u : par[u]= leader(par[u]); }
 bool unite(int u, int v) {
  if ((u= leader(u)) == (v= leader(v))) return false;
  if (par[u] > par[v]) std::swap(u, v);
  return par[u]+= par[v], par[v]= u, true;
 }
 bool connected(int u, int v) { return leader(u) == leader(v); }
 int size(int u) { return -par[leader(u)]; }
};

#line 2 "src/DataStructure/UnionFind.hpp"
#include <vector>
#include <algorithm>
class UnionFind {
 std::vector<int> par;
public:
 UnionFind(int n): par(n, -1) {}
 int leader(int u) { return par[u] < 0 ? u : par[u]= leader(par[u]); }
 bool unite(int u, int v) {
  if ((u= leader(u)) == (v= leader(v))) return false;
  if (par[u] > par[v]) std::swap(u, v);
  return par[u]+= par[v], par[v]= u, true;
 }
 bool connected(int u, int v) { return leader(u) == leader(v); }
 int size(int u) { return -par[leader(u)]; }
};

Union-Find (src/DataStructure/UnionFind.hpp)

UnionFind クラス

Required by

Verified with

Code

`UnionFind` クラス