UnionFind with potential
(data_structure/unionfind_with_potential.hpp)

• View this file on GitHub
• Last update: 2023-11-13 02:30:46+09:00
• Include: #include "data_structure/unionfind_with_potential.hpp"

説明

ポテンシャル付きUnionFind。ここで、 $\alpha(N)$ をアッカーマン関数の逆関数とする。

same(int x, int y)

$x$ と $y$ が同じグループか判定。 $O(\alpha(N))$

merge(int x, int y, T p)

$x$ のグループと $y$ のグループをマージ。ポテンシャルは $potential(x) = potential(y) + p$ とする。 $O(\alpha(N))$

leader(int x)

$x$ のグループの代表を返す。 $O(\alpha(N))$

size(int x)

$x$ のグループのサイズを返す。 $O(\alpha(N))$

potential(int x)

$x$ のポテンシャルを返す。 $O(\alpha(N))$

diff(int x, int y)

$x$ と $y$ のポテンシャルの差分を返す。 $O(\alpha(N))$

Code

#pragma once

#include <cassert>
#include <vector>

namespace ebi {

template <class T> struct unionfind_with_potential {
  public:
    unionfind_with_potential(int n) : data_(n, -1), potential_(n, T()) {}

    bool same(int x, int y) {
        return leader(x) == leader(y);
    }

    // potential(x) = potential(y) + p
    bool merge(int x, int y, T p) {
        p = potential(x) - p - potential(y);
        x = leader(x);
        y = leader(y);
        if (x == y) return p == T();
        if (data_[x] > data_[y]) {
            std::swap(x, y);
            p = -p;
        }
        data_[x] += data_[y];
        data_[y] = x;
        potential_[y] = p;
        return true;
    }

    int leader(int x) {
        if (data_[x] < 0) return x;
        int l = leader(data_[x]);
        potential_[x] = potential_[data_[x]] + potential_[x];
        return data_[x] = l;
    }

    int size(int x) {
        return -data_[leader(x)];
    }

    T potential(int x) {
        leader(x);
        return potential_[x];
    }

    T diff(int x, int y) {
        return potential(x) - potential(y);
    }

  private:
    std::vector<int> data_;
    std::vector<T> potential_;
};

}  // namespace ebi

#line 2 "data_structure/unionfind_with_potential.hpp"

#include <cassert>
#include <vector>

namespace ebi {

template <class T> struct unionfind_with_potential {
  public:
    unionfind_with_potential(int n) : data_(n, -1), potential_(n, T()) {}

    bool same(int x, int y) {
        return leader(x) == leader(y);
    }

    // potential(x) = potential(y) + p
    bool merge(int x, int y, T p) {
        p = potential(x) - p - potential(y);
        x = leader(x);
        y = leader(y);
        if (x == y) return p == T();
        if (data_[x] > data_[y]) {
            std::swap(x, y);
            p = -p;
        }
        data_[x] += data_[y];
        data_[y] = x;
        potential_[y] = p;
        return true;
    }

    int leader(int x) {
        if (data_[x] < 0) return x;
        int l = leader(data_[x]);
        potential_[x] = potential_[data_[x]] + potential_[x];
        return data_[x] = l;
    }

    int size(int x) {
        return -data_[leader(x)];
    }

    T potential(int x) {
        leader(x);
        return potential_[x];
    }

    T diff(int x, int y) {
        return potential(x) - potential(y);
    }

  private:
    std::vector<int> data_;
    std::vector<T> potential_;
};

}  // namespace ebi

Back to top page