partially persistent unionfind
(data_structure/partially_persistent_unionfind.hpp)

• View this file on GitHub
• Last update: 2024-05-28 15:39:48+09:00
• Include: #include "data_structure/partially_persistent_unionfind.hpp"
• Link: https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/21131946
• Link: https://noshi91.hatenablog.com/entry/2018/02/18/161529

説明

find(t, v)

時刻 $t$ での $v$ の親を返す。 $O(\log N)$

merge(a, b)

$a$ と $b$ のグループをマージする。 $O(\log N)$

same(t, a, b)

時刻 $t$ で $a$ と $b$ が同じグループに属するか判定する。 $O(\log N)$

Code

#pragma once

#include <algorithm>

#include <limits>

#include <vector>


/*
    refernce: https://noshi91.hatenablog.com/entry/2018/02/18/161529
    verify:
   https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/21131946
*/

namespace ebi {

struct partially_persistent_unionfind {
  private:
    int now = 0;
    std::vector<int> par, time;
    std::vector<std::vector<std::pair<int, int>>> data;

  public:
    partially_persistent_unionfind(int n)
        : par(n, 1), time(n, std::numeric_limits<int>::max()), data(n) {
        for (auto &v : data) {
            v.emplace_back(0, 1);
        }
    }

    int find(int t, int v) {
        if (time[v] > t)
            return v;
        else
            return find(t, par[v]);
    }

    bool merge(int a, int b) {
        ++now;
        a = find(now, a);
        b = find(now, b);
        if (a == b) return false;
        if (par[a] < par[b]) std::swap(a, b);
        par[a] += par[b];
        data[a].emplace_back(now, par[a]);
        par[b] = a;
        time[b] = now;
        return true;
    }

    bool same(int t, int a, int b) {
        return find(t, a) == find(t, b);
    }

    int size(int t, int v) {
        v = find(t, v);
        return std::prev(
                   std::upper_bound(
                       data[v].begin(), data[v].end(),
                       std::pair<int, int>(t, std::numeric_limits<int>::max())))
            ->second;
    }
};

}  // namespace ebi

#line 2 "data_structure/partially_persistent_unionfind.hpp"

#include <algorithm>

#include <limits>

#include <vector>


/*
    refernce: https://noshi91.hatenablog.com/entry/2018/02/18/161529
    verify:
   https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/21131946
*/

namespace ebi {

struct partially_persistent_unionfind {
  private:
    int now = 0;
    std::vector<int> par, time;
    std::vector<std::vector<std::pair<int, int>>> data;

  public:
    partially_persistent_unionfind(int n)
        : par(n, 1), time(n, std::numeric_limits<int>::max()), data(n) {
        for (auto &v : data) {
            v.emplace_back(0, 1);
        }
    }

    int find(int t, int v) {
        if (time[v] > t)
            return v;
        else
            return find(t, par[v]);
    }

    bool merge(int a, int b) {
        ++now;
        a = find(now, a);
        b = find(now, b);
        if (a == b) return false;
        if (par[a] < par[b]) std::swap(a, b);
        par[a] += par[b];
        data[a].emplace_back(now, par[a]);
        par[b] = a;
        time[b] = now;
        return true;
    }

    bool same(int t, int a, int b) {
        return find(t, a) == find(t, b);
    }

    int size(int t, int v) {
        v = find(t, v);
        return std::prev(
                   std::upper_bound(
                       data[v].begin(), data[v].end(),
                       std::pair<int, int>(t, std::numeric_limits<int>::max())))
            ->second;
    }
};

}  // namespace ebi

Back to top page