potentialized_unionfind (ポテンシャル付きUnion Find木)
(src/dataStructure/potentialized_unionfind.hpp)

• View this file on GitHub
• Last update: 2022-12-05 12:46:01+09:00
• Include: #include "src/dataStructure/potentialized_unionfind.hpp"

概要

直線上のN個の点について、点Aが点Bより正方向にdだけ離れているといった情報を保持できるデータ構造です。

UnionFindアルゴリズムを応用することで実装しています。

機能

• potentialized_unionfind<cost_type> (std::size_t n)
  • コンストラクタ
  • cost_type: dの型
    • 加法単位元と加法逆元が存在する必要があります
    • 0 と *= -1があればコンパイルは通るはず（？）
  • n:点数N
  • 計算量: $O(n)$
• int leader(int x)
  • 点xが属する根付き木の根を返します
  • x: $0\ \le\ x\ \le\ n$
  • 計算量:
• bool same(int x, int y)
  • 点xと点yが連結かを返します
  • x: $0\ \le\ x\ \le\ n$
  • y: $0\ \le\ y\ \le\ n$
  • 計算量:
• bool merge(int x, int y, cost_type w)
  • 「点xから正方向にw離れた所に点yがある」という情報を追加します。
    • 矛盾した情報を与えた場合の動作は未定義です。
    • クエリに矛盾する情報があるかもしれない時はtest/potentialized_unionfind3.test.cppみたいな感じで別途処理してください
  • x: $0\ \le\ x\ \le\ n$
  • y: $0\ \le\ y\ \le\ n$
  • same(x, y) == falseの時この関数はtrueを返します
  • 計算量:
• cost_type diff(int y, int x)
  • 点xから点yへ正方向にどれだけ離れているかを返します。
    • same(x, y) == falseの時の動作は未定義です。
  • x: $0\ \le\ x\ \le\ n$
  • y: $0\ \le\ y\ \le\ n$
  • 計算量:

参考

重み付き Union-Find 木とそれが使える問題のまとめ、および、牛ゲーについて

Verified with

• test/potentialized_unionfind1.test.cpp
• test/potentialized_unionfind2.test.cpp
• test/potentialized_unionfind3.test.cpp

Code

#pragma once

#include <vector>
#include <utility>

namespace zawa {

template <class cost_type>
class potentialized_unionfind {
private:
    std::vector<int> parents;
    std::vector<int> sizes;
    std::vector<cost_type> weights;

    int rooting(int x) {
        if (parents[x] == x) {
            return x;
        }
        else {
            int root = rooting(parents[x]);
            weights[x] += weights[parents[x]];
            return parents[x] = root;
        }
    }

    cost_type get_weight(int x) {
        rooting(x);
        return weights[x];
    }

public:

    potentialized_unionfind(std::size_t n) : parents(n, 0), sizes(n, 1), weights(n) {
        for (std::size_t i = 0 ; i < n ; i++) {
            parents[i] = i;
        }
    }

    int leader(int x) {
        return rooting(x);
    }

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

    bool merge(int x, int y, cost_type w) {
        w += get_weight(x);
        w -= get_weight(y);
        int rx = rooting(x), ry = rooting(y);
        if (rx == ry) {
            return false;
        }
        if (sizes[rx] < sizes[ry]) {
            std::swap(rx, ry);
            w *= -1;
        }
        sizes[rx] += sizes[ry];
        parents[ry] = rx;
        weights[ry] = w;
        return true;
    }

    cost_type diff(int y, int x) {
        return get_weight(y) - get_weight(x);
    }
};

} // namespace zawa

#line 2 "src/dataStructure/potentialized_unionfind.hpp"

#include <vector>
#include <utility>

namespace zawa {

template <class cost_type>
class potentialized_unionfind {
private:
    std::vector<int> parents;
    std::vector<int> sizes;
    std::vector<cost_type> weights;

    int rooting(int x) {
        if (parents[x] == x) {
            return x;
        }
        else {
            int root = rooting(parents[x]);
            weights[x] += weights[parents[x]];
            return parents[x] = root;
        }
    }

    cost_type get_weight(int x) {
        rooting(x);
        return weights[x];
    }

public:

    potentialized_unionfind(std::size_t n) : parents(n, 0), sizes(n, 1), weights(n) {
        for (std::size_t i = 0 ; i < n ; i++) {
            parents[i] = i;
        }
    }

    int leader(int x) {
        return rooting(x);
    }

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

    bool merge(int x, int y, cost_type w) {
        w += get_weight(x);
        w -= get_weight(y);
        int rx = rooting(x), ry = rooting(y);
        if (rx == ry) {
            return false;
        }
        if (sizes[rx] < sizes[ry]) {
            std::swap(rx, ry);
            w *= -1;
        }
        sizes[rx] += sizes[ry];
        parents[ry] = rx;
        weights[ry] = w;
        return true;
    }

    cost_type diff(int y, int x) {
        return get_weight(y) - get_weight(x);
    }
};

} // namespace zawa

Back to top page