永続Union-Find (lib/persistent_ds/persistent_union_find.hpp)

• View this file on GitHub
• Last update: 2025-11-08 10:27:08+09:00
• Include: #include "lib/persistent_ds/persistent_union_find.hpp"

Depends on

• 永続配列 (lib/persistent_ds/persistent_array.hpp)

Verified with

• test/yosupo/data_structure/persistent_union_find.test.cpp

Code

#pragma once
#include <utility>
#include "persistent_ds/persistent_array.hpp"

/// @brief 永続Union-Find
struct persistent_union_find {
    constexpr persistent_union_find() : data() {}
    persistent_union_find(const persistent_array<int> &_data) : data(_data) {}
    persistent_union_find(int n) : data(n, -1) {}

    int root(int x) const {
        int y = data[x];
        return y < 0 ? x : root(y);
    }
    int get_root(int x) const { return root(x); }

    bool is_root(int x) const { return data[x] < 0; }

    persistent_union_find unite(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return *this;
        int a = data[x], b = data[y];
        if (a > b) std::swap(x, y);
        return persistent_union_find(data.set(x, a + b).set(y, x));
    }

    int size(int x) const { return -(data[root(x)]); }
    int get_size(int x) const { return size(x); }

    bool same(int x, int y) const { return root(x) == root(y); }
    bool is_same(int x, int y) const { return same(x, y); }

  private:
    persistent_array<int> data;
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: persistent_ds/persistent_array.hpp: line -1: no such header

Back to top page