Persistent Union Find
(data-structure/unionfind/persistent_union_find.hpp)

• View this file on GitHub
• Last update: 2024-01-07 20:49:49+09:00
• Include: #include "data-structure/unionfind/persistent_union_find.hpp"

Description

永続 union find は，過去のバージョンを保持する union find である．

空間計算量: $O(n + m \log n)$, $m$ は変更の数

Operations

• PersistentUnionFind(int n)
  • サイズn の永続 union find を構築する
  • 時間計算量: $O(n \log n)$
• int find(int x)
  • $x$ が属する木の根を返す
  • 時間計算量: $O(\log^2 n)$
• PersistentUnionFind unite(int x, int y)
  • $x$ が属する集合と $y$ が属する集合を連結する
  • 時間計算量: $O(\log^2 n)$
• bool same(int x, int y)
  • $x$ と $y$ が同じ集合に属するかを判定する
  • 時間計算量: $O(\log^2 n)$
• int size(int x)
  • $x$ が属する集合の大きさを返す
  • 時間計算量: $O(\log^2 n)$

Reference

• A Persistent Union-Find Data Structure

Depends on

• Persistent Array (data-structure/persistent_array.hpp)

Verified with

• test/yosupo/persistent_unionfind.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>

#include "../persistent_array.hpp"

class PersistentUnionFind {
   public:
    PersistentUnionFind() = default;
    explicit PersistentUnionFind(int n) : data(std::vector<int>(n, -1)) {}

    int find(int x) const {
        int p = data.get(x);
        if (p < 0) return x;
        return find(p);
    }

    PersistentUnionFind unite(int x, int y) const {
        x = find(x);
        y = find(y);
        if (x == y) return *this;
        int u = data.get(x);
        int v = data.get(y);
        if (u > v) std::swap(x, y);
        auto tmp = data.set(x, u + v);
        auto res = tmp.set(y, x);
        return PersistentUnionFind(res);
    }

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

    int size(int x) const { return -data.get(x); }

   private:
    PersistentArray<int, 8> data;

    explicit PersistentUnionFind(const PersistentArray<int, 8>& pa)
        : data(pa) {}
};

#line 2 "data-structure/unionfind/persistent_union_find.hpp"
#include <algorithm>
#include <vector>

#line 2 "data-structure/persistent_array.hpp"
#include <memory>
#line 4 "data-structure/persistent_array.hpp"

template <typename T, int B = 2>
class PersistentArray {
   public:
    PersistentArray() = default;
    explicit PersistentArray(const std::vector<T>& v) {
        for (int i = 0; i < (int)v.size(); ++i) root = set(root, i, v[i]);
    }

    T get(int k) const { return get(root, k); }

    PersistentArray set(int k, const T& x) const {
        return PersistentArray(set(root, k, x));
    }

   private:
    struct Node;
    using node_ptr = std::shared_ptr<Node>;

    struct Node {
        T val;
        node_ptr ch[B];
    };

    node_ptr root = nullptr;

    explicit PersistentArray(const node_ptr& root) : root(root) {}

    T get(const node_ptr& t, int k) const {
        if (k == 0) return t->val;
        return get(t->ch[k % B], k / B);
    }

    node_ptr set(const node_ptr& t, int k, const T& x) const {
        node_ptr res =
            t ? std::make_shared<Node>(*t) : std::make_shared<Node>();
        if (k == 0) {
            res->val = x;
        } else {
            res->ch[k % B] = set(res->ch[k % B], k / B, x);
        }
        return res;
    }
};
#line 6 "data-structure/unionfind/persistent_union_find.hpp"

class PersistentUnionFind {
   public:
    PersistentUnionFind() = default;
    explicit PersistentUnionFind(int n) : data(std::vector<int>(n, -1)) {}

    int find(int x) const {
        int p = data.get(x);
        if (p < 0) return x;
        return find(p);
    }

    PersistentUnionFind unite(int x, int y) const {
        x = find(x);
        y = find(y);
        if (x == y) return *this;
        int u = data.get(x);
        int v = data.get(y);
        if (u > v) std::swap(x, y);
        auto tmp = data.set(x, u + v);
        auto res = tmp.set(y, x);
        return PersistentUnionFind(res);
    }

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

    int size(int x) const { return -data.get(x); }

   private:
    PersistentArray<int, 8> data;

    explicit PersistentUnionFind(const PersistentArray<int, 8>& pa)
        : data(pa) {}
};

Back to top page