Potentialized UnionFind （重み付き UnionFind）
(unionfind/potentialized_unionfind.hpp)

• View this file on GitHub
• Last update: 2024-10-02 23:55:49+09:00
• Include: #include "unionfind/potentialized_unionfind.hpp"

2個の要素間の重みづけが可能な UnionFind．

使用方法

ポテンシャルが（ふつうの）整数の場合．

PotentializedUnionFind<int> uf(N);
uf.unite(s, t, diff);  // f[t] = f[s] + diff を要請．これまでの要請と矛盾すれば false を返す．

auto x = uf.diff(s, t);  // f[t] - f[s] （として考えられる値の一つ）を出力．

ポテンシャルが $\mathbb{F}_{2}$ 上のベクトルの場合．

PotentializedUnionFind<Nimber> uf(N);

問題例

• No.1420 国勢調査 (Easy) - yukicoder $\mathbb{F}_2$ 上のベクトル．
• AtCoder Beginner Contest 373 D - Hidden Weights

Verified with

• unionfind/test/potentialized_unionfind.test.cpp
• unionfind/test/potentialized_unionfind_F2.yuki1420.test.cpp
• unionfind/test/potentialized_unionfind_int.aoj3142.test.cpp

Code

#pragma once
#include <numeric>
#include <utility>
#include <vector>

// Potentialized UnionFind (Weighted UnionFind)
template <class S> struct PotentializedUnionFind {
    std::vector<int> par, sz;
    std::vector<S> pot;
    PotentializedUnionFind(int N = 0) : par(N), sz(N, 1), pot(N) {
        std::iota(par.begin(), par.end(), 0);
    }
    int find(int x) {
        if (par[x] != x) {
            int r = find(par[x]);
            pot[x] = pot[x] + pot[par[x]], par[x] = r;
        }
        return par[x];
    }
    bool unite(int s, int t, S rel_diff) {
        // Relate s and t by f[t] = f[s] + rel_diff
        // Return false iff contradiction happens.
        rel_diff = rel_diff + weight(s) + (-weight(t));
        if ((s = find(s)) == (t = find(t))) return rel_diff == 0;
        if (sz[s] < sz[t]) std::swap(s, t), rel_diff = -rel_diff;
        par[t] = s, sz[s] += sz[t], pot[t] = rel_diff;
        return true;
    }
    S weight(int x) { return find(x), pot[x]; }
    S diff(int s, int t) { return weight(t) + (-weight(s)); } // return f[t] - f[s]
    int count(int x) { return sz[find(x)]; }
    bool same(int s, int t) { return find(s) == find(t); }
};

#line 2 "unionfind/potentialized_unionfind.hpp"
#include <numeric>
#include <utility>
#include <vector>

// Potentialized UnionFind (Weighted UnionFind)
template <class S> struct PotentializedUnionFind {
    std::vector<int> par, sz;
    std::vector<S> pot;
    PotentializedUnionFind(int N = 0) : par(N), sz(N, 1), pot(N) {
        std::iota(par.begin(), par.end(), 0);
    }
    int find(int x) {
        if (par[x] != x) {
            int r = find(par[x]);
            pot[x] = pot[x] + pot[par[x]], par[x] = r;
        }
        return par[x];
    }
    bool unite(int s, int t, S rel_diff) {
        // Relate s and t by f[t] = f[s] + rel_diff
        // Return false iff contradiction happens.
        rel_diff = rel_diff + weight(s) + (-weight(t));
        if ((s = find(s)) == (t = find(t))) return rel_diff == 0;
        if (sz[s] < sz[t]) std::swap(s, t), rel_diff = -rel_diff;
        par[t] = s, sz[s] += sz[t], pot[t] = rel_diff;
        return true;
    }
    S weight(int x) { return find(x), pot[x]; }
    S diff(int s, int t) { return weight(t) + (-weight(s)); } // return f[t] - f[s]
    int count(int x) { return sz[find(x)]; }
    bool same(int s, int t) { return find(s) == find(t); }
};

Back to top page