Union-Find (ポテンシャル) (src/DataStructure/UnionFind_Potentialized.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_Potentialized.hpp"

`UnionFind_Potentialized<weight_t>`　クラス

重み(ポテンシャル)付きUnion-Find．
各要素 $u$ にポテンシャル $p(u)$ ( weight_t型 )を持たせ，同じ集合に属する任意の2要素 $u,v$ についてポテンシャルの差分 $p(v)-p(u)$ を計算できるようにする．
weight_t型は weight_t(),operator+(a,b),operator-(a),operator-(a,b) によって群になれば使える．
weight_t=bool のときは $\mathbb{F}_2$ の意味で使われる．

非可換な群でも動く．その場合計算順序に注意．
unite(u,v,w)は $p(u) = p(v) + w$ すなわち $-p(v)+p(u)=w$ を満たし，diff(u,v) は $-p(v)+p(u)$ を返す．

以下，$\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,w)`	要素 $u,v$ それぞれが属する集合を併合し，ポテンシャルについては $p(u)=p(v)+w$ を満たすように変更する．矛盾していたら`false` を返す．	$O(\alpha(n))$
`potential(u)`	要素 $u$ のポテンシャル $p(u)$ を返す．	$O(\alpha(n))$
`diff(u,v)`	$-p(v)+p(u)$ を返す	$O(\alpha(n))$

Verify

yukicoder No.1420 国勢調査 (Easy) (ポテンシャル, xor, sp judge)\
競プロ典型 90 問　068 - Paired Information（★5） (affine, 非可換群)

Verified with

Code

#pragma once
#include <vector>
#include <algorithm>
#include <cassert>
template <class weight_t> class UnionFind_Potentialized {
 std::vector<int> par;
 std::vector<weight_t> val;
public:
 UnionFind_Potentialized(int n): par(n, -1), val(n) {}
 int leader(int u) {
  if (par[u] < 0) return u;
  int r= leader(par[u]);
  if constexpr (std::is_same_v<weight_t, bool>) val[u]= val[u] ^ val[par[u]];
  else val[u]= val[par[u]] + val[u];
  return par[u]= r;
 }
 //  -p(v) + p(u) = w
 bool unite(int u, int v, weight_t w) {
  int a= leader(u), b= leader(v);
  if constexpr (std::is_same_v<weight_t, bool>) w^= val[u] ^ val[v];
  else w= val[v] + w - val[u];
  if (a == b) return w == weight_t();
  if (par[b] > par[a]) std::swap(a, b), w= -w;
  return par[b]+= par[a], par[a]= b, val[a]= w, true;
 }
 bool connected(int u, int v) { return leader(u) == leader(v); }
 int size(int u) { return -par[leader(u)]; }
 weight_t potential(int u) { return leader(u), val[u]; }
 //  -p(v) + p(u)
 weight_t diff(int u, int v) {
  if constexpr (std::is_same_v<weight_t, bool>) return potential(u) ^ potential(v);
  else return -potential(v) + potential(u);
 }
};

#line 2 "src/DataStructure/UnionFind_Potentialized.hpp"
#include <vector>
#include <algorithm>
#include <cassert>
template <class weight_t> class UnionFind_Potentialized {
 std::vector<int> par;
 std::vector<weight_t> val;
public:
 UnionFind_Potentialized(int n): par(n, -1), val(n) {}
 int leader(int u) {
  if (par[u] < 0) return u;
  int r= leader(par[u]);
  if constexpr (std::is_same_v<weight_t, bool>) val[u]= val[u] ^ val[par[u]];
  else val[u]= val[par[u]] + val[u];
  return par[u]= r;
 }
 //  -p(v) + p(u) = w
 bool unite(int u, int v, weight_t w) {
  int a= leader(u), b= leader(v);
  if constexpr (std::is_same_v<weight_t, bool>) w^= val[u] ^ val[v];
  else w= val[v] + w - val[u];
  if (a == b) return w == weight_t();
  if (par[b] > par[a]) std::swap(a, b), w= -w;
  return par[b]+= par[a], par[a]= b, val[a]= w, true;
 }
 bool connected(int u, int v) { return leader(u) == leader(v); }
 int size(int u) { return -par[leader(u)]; }
 weight_t potential(int u) { return leader(u), val[u]; }
 //  -p(v) + p(u)
 weight_t diff(int u, int v) {
  if constexpr (std::is_same_v<weight_t, bool>) return potential(u) ^ potential(v);
  else return -potential(v) + potential(u);
 }
};

Union-Find (ポテンシャル) (src/DataStructure/UnionFind_Potentialized.hpp)

UnionFind_Potentialized<weight_t> クラス

Verify

Verified with

Code

`UnionFind_Potentialized<weight_t>`　クラス