ポテンシャル付き Union Find
(union-find/potentialized-union-find.hpp)

• View this file on GitHub
• Last update: 2025-10-24 10:50:32+09:00
• Include: #include "union-find/potentialized-union-find.hpp"

通常の Union Find のほかに列 $(p_0,p_1,\dots,p_{n-1})$ に関する情報を管理する．

• unite(u, v, w)：$p_u-p_v=w$ という情報が与えられる．それまでに与えられた valid な情報と矛盾しないとき valid な情報と呼ぶことにする．与えられた情報が valid な情報か否かを返す．
• diff(u, v)：$p_u-p_v$ の値が valid な情報から一意に定まる場合その値を，定まらない場合はその旨を報告する．

アルゴリズム

Union Find の内部において $p_v$ から $v$ を含む連結成分の根の $p$ の値を減じたものを管理する．

Verified with

• verify/union-find/LC_unionfind_with_potential.test.cpp

Code

#pragma once

template <class T>
struct PotentializedUnionFind {
 private:
  vector<int> a;
  vector<T> p;

 public:
  PotentializedUnionFind(int n) : a(n, -1), p(n, 0) {}
  int find(int v) {
    if (a[v] < 0) return v;
    int r = find(a[v]);
    p[v] += p[a[v]];
    return a[v] = r;
  }
  int size(int v) { return -a[find(v)]; }
  bool same(int u, int v) { return find(u) == find(v); }
  // p[u]-p[v]=w
  bool unite(int u, int v, T w) {
    int x = find(u), y = find(v);
    if (x == y) return p[u] - p[v] == w;
    w -= p[u], w += p[v];
    if (a[x] < a[y]) {
      p[y] = p[x] - w;
      a[x] += a[y];
      a[y] = x;
    } else {
      p[x] = p[y] + w;
      a[y] += a[x];
      a[x] = y;
    }
    return true;
  }
  // p[u]-p[v]
  T diff(int u, int v) { return p[u] - p[v]; }
};
/**
 * @brief ポテンシャル付き Union Find
 * @docs docs/union-find/potentialized-union-find.md
 */

#line 2 "union-find/potentialized-union-find.hpp"

template <class T>
struct PotentializedUnionFind {
 private:
  vector<int> a;
  vector<T> p;

 public:
  PotentializedUnionFind(int n) : a(n, -1), p(n, 0) {}
  int find(int v) {
    if (a[v] < 0) return v;
    int r = find(a[v]);
    p[v] += p[a[v]];
    return a[v] = r;
  }
  int size(int v) { return -a[find(v)]; }
  bool same(int u, int v) { return find(u) == find(v); }
  // p[u]-p[v]=w
  bool unite(int u, int v, T w) {
    int x = find(u), y = find(v);
    if (x == y) return p[u] - p[v] == w;
    w -= p[u], w += p[v];
    if (a[x] < a[y]) {
      p[y] = p[x] - w;
      a[x] += a[y];
      a[y] = x;
    } else {
      p[x] = p[y] + w;
      a[y] += a[x];
      a[x] = y;
    }
    return true;
  }
  // p[u]-p[v]
  T diff(int u, int v) { return p[u] - p[v]; }
};
/**
 * @brief ポテンシャル付き Union Find
 * @docs docs/union-find/potentialized-union-find.md
 */

Back to top page