(offine) Functional Graph 上の頂点 $v$ から $k$ 回移動した先の頂点 (Offline Jump On Functional Graph)
(src/graph/functional-graph/offline-query/offline-query-jump-on-functional-graph.hpp)

View this file on GitHub
Last update: 2023-07-30 00:54:52+09:00
Include: #include "src/graph/functional-graph/offline-query/offline-query-jump-on-functional-graph.hpp"

Functional Graph において、頂点 $v$ からちょうど $k$ 本の辺を辿って到達する頂点を求めるクエリをオフラインで処理する。このようなクエリを $jump(v, k)$ と表記する。

Appendix

コンストラクタ

OfflineJumpOnFunctionalGraphQuery(const G &g)

$jump$ クエリを求めるグラフ $g$ を渡す。

内部では $g$ を loop と tree に分解している。

制約

$g$ は Functional Graph である。
- $g$ の任意の任意の頂点の出次数は $1$ であるとも言い換えられる。

計算量

$O(|V|)$

add_query

void add_query(usize v, u64 k)

$jump(v, k)$ を求めるクエリを追加する。

後述する build をした後、jump(v, k) によってクエリに対する答えを得ることができる。

制約

$0 \leq v < |V|$

計算量

$O(1)$

build

void build()

$g$ 上での $jump$ クエリを計算する。

計算量

$O(|V| + Q)$
- 追加されたクエリの数を $Q$ とする

jump

usize jump(usize v, u64 k)

$jump(v, k)$ を返す。

制約

add_query(v, k) が呼ばれており、かつその後に build() が呼ばれていること。

計算量

$O(1)$

Depends on

Verified with

Code

#pragma once

#include "src/cpp-template/header/int-alias.hpp"
#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/graph/tree/offline-query/offline-query-level-ancestor.hpp"
#include "src/utility/pair-hash.hpp"

#include <cassert>
#include <unordered_map>
#include <utility>
#include <vector>

namespace luz {

  template < class G >
  class OfflineJumpOnFunctionalGraphQuery {
    using graph     = G;
    using cost_type = typename graph::cost_type;

    usize g_size;
    graph g;

    graph tree;
    usize tree_root;
    std::vector< usize > tree_depth, subtree_roots;

    std::vector< usize > loop_id, loop_size, loop_pos;
    std::vector< std::vector< usize > > loops;

    using query_type = std::pair< usize, u64 >;
    std::vector< query_type > qs;
    std::unordered_map< query_type, usize, PairHash > result;

    void dfs_on_subtree(usize v, usize p) {
      for (auto &e: tree[v]) {
        usize u = e.to;
        if (u == p) continue;
        subtree_roots[u] = subtree_roots[v];
        tree_depth[u]    = tree_depth[v] + 1;
        dfs_on_subtree(u, v);
      }
    }

    std::vector< usize > get_indegrees() const {
      std::vector< usize > indegrees(g_size);
      for (usize v: rep(0, g_size)) {
        for (auto e: g[v]) {
          indegrees[e.to]++;
        }
      }
      return indegrees;
    }

    void construct_tree(std::vector< usize > &indegrees) {
      std::vector< usize > leaves;
      leaves.reserve(g_size);

      for (usize v: rep(0, g_size)) {
        if (indegrees[v] > 0) {
          continue;
        }
        leaves.emplace_back(v);
      }

      while (not leaves.empty()) {
        usize child = leaves.back();
        leaves.pop_back();

        usize parent = g[child][0].to;
        indegrees[parent]--;

        tree.add_undirected_edge(parent, child);

        if (indegrees[parent] == 0) {
          leaves.emplace_back(parent);
        }
      }

      for (usize v: rep(0, g_size)) {
        if (indegrees[v] == 0) {
          continue;
        }
        tree.add_undirected_edge(tree_root, v);
      }

      tree.initialize();

      for (usize v: rep(0, g_size)) {
        if (indegrees[v] == 0) {
          continue;
        }
        subtree_roots[v] = v;
        dfs_on_subtree(v, tree_root);
      }
    }

    void construct_loops(std::vector< usize > &indegrees) {
      for (usize v: rep(0, g_size)) {
        if (indegrees[v] == 0) {
          continue;
        }

        usize cur = v;
        std::vector< usize > loop;
        do {
          loop_id[cur]  = loops.size();
          loop_pos[cur] = loop.size();
          loop.emplace_back(cur);
          indegrees[cur] = 0;
          cur            = g[cur][0].to;
        } while (cur != v);

        do {
          loop_size[cur] = loop.size();
          cur            = g[cur][0].to;
        } while (cur != v);

        loops.emplace_back(std::move(loop));
      }
    }

   public:
    explicit OfflineJumpOnFunctionalGraphQuery(const graph &g_)
        : g_size(g_.size()),
          g(g_),
          tree(g_size + 1),
          tree_root(g_size),
          tree_depth(g_size),
          subtree_roots(g_size),
          loop_id(g_size),
          loop_size(g_size),
          loop_pos(g_size) {
      for (usize v: rep(0, g_size)) {
        assert(g[v].size() == 1);
      }

      std::vector< usize > indegrees = get_indegrees();
      construct_tree(indegrees);
      construct_loops(indegrees);
    }

    void add_query(usize v, u64 k) {
      qs.emplace_back(v, k);
    }

    void build() {
      OfflineLAQuery la_solver(tree);
      result.reserve(qs.size());
      for (auto [v, k]: qs) {
        if (k < tree_depth[v]) {
          la_solver.add_query(v, tree_depth[v] - k + 1);
        } else {
          query_type qi(v, k);
          k -= tree_depth[v];
          usize root       = subtree_roots[v];
          const auto &loop = loops[loop_id[root]];
          k += loop_pos[root];
          k %= loop_size[root];
          result[qi] = loop[k];
        }
      }
      la_solver.build(g_size);

      for (auto [v, k]: qs) {
        if (tree_depth[v] <= k) {
          continue;
        }
        query_type qi(v, k);
        result[qi] = la_solver.la(v, tree_depth[v] - k + 1).value();
      }
    }

    usize jump(usize v, u64 k) const {
      query_type qi(v, k);
      assert(result.count(qi));
      return result.find(qi)->second;
    }
  };
} // namespace luz

#line 2 "src/graph/functional-graph/offline-query/offline-query-jump-on-functional-graph.hpp"

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32  = std::int32_t;
  using i64  = std::int64_t;
  using i128 = __int128_t;

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 2 "src/graph/tree/offline-query/offline-query-level-ancestor.hpp"

#line 2 "src/utility/pair-hash.hpp"

#line 4 "src/utility/pair-hash.hpp"

#include <functional>
#include <utility>

namespace luz {

  class PairHash {
    template < typename T >
    usize hash_combine(usize hr, const T &x) const {
      usize h = std::hash< T >()(x);
      return hr ^ (h + (hr << 11) + (hr >> 13));
    }

   public:
    template < typename F, typename S >
    usize operator()(const std::pair< F, S > &p) const {
      return hash_combine(hash_combine(0, p.first), p.second);
    }
  };

} // namespace luz
#line 6 "src/graph/tree/offline-query/offline-query-level-ancestor.hpp"

#include <cassert>
#include <optional>
#include <unordered_map>
#line 11 "src/graph/tree/offline-query/offline-query-level-ancestor.hpp"
#include <vector>

namespace luz {

  template < class G >
  class OfflineLAQuery {
    using graph     = G;
    using cost_type = typename graph::cost_type;

    usize g_size;
    graph g;

    usize query_count;
    std::vector< std::vector< usize > > qs;

    std::vector< bool > visited;
    std::vector< usize > path;

    using query_type = std::pair< usize, usize >;
    std::unordered_map< query_type, std::optional< usize >, PairHash >
        results;

    void bound_check(usize v) const {
      assert(v < g_size);
    }

    void dfs(usize v) {
      visited[v] = true;
      path.emplace_back(v);

      for (const auto &level: qs[v]) {
        if (level < path.size()) {
          results[query_type(v, level)] = path[level];
        }
      }

      for (const auto &e: g[v]) {
        if (visited[e.to]) continue;
        dfs(e.to);
      }

      path.pop_back();
    }

   public:
    explicit OfflineLAQuery() = default;

    explicit OfflineLAQuery(graph &g)
        : g_size(g.size()),
          g(g),
          query_count(0),
          qs(g_size),
          visited(g_size, false) {}

    void add_query(usize v, usize level) {
      bound_check(v);
      qs[v].emplace_back(level);
      query_count++;
    }

    void build(usize root) {
      bound_check(root);
      results.reserve(query_count);
      path.reserve(g_size);
      dfs(root);
    }

    std::optional< usize > la(usize v, usize level) const {
      bound_check(v);
      query_type qi(v, level);
      assert(results.count(qi));
      return (*results.find(qi)).second;
    }
  };

} // namespace luz
#line 8 "src/graph/functional-graph/offline-query/offline-query-jump-on-functional-graph.hpp"

#line 13 "src/graph/functional-graph/offline-query/offline-query-jump-on-functional-graph.hpp"

namespace luz {

  template < class G >
  class OfflineJumpOnFunctionalGraphQuery {
    using graph     = G;
    using cost_type = typename graph::cost_type;

    usize g_size;
    graph g;

    graph tree;
    usize tree_root;
    std::vector< usize > tree_depth, subtree_roots;

    std::vector< usize > loop_id, loop_size, loop_pos;
    std::vector< std::vector< usize > > loops;

    using query_type = std::pair< usize, u64 >;
    std::vector< query_type > qs;
    std::unordered_map< query_type, usize, PairHash > result;

    void dfs_on_subtree(usize v, usize p) {
      for (auto &e: tree[v]) {
        usize u = e.to;
        if (u == p) continue;
        subtree_roots[u] = subtree_roots[v];
        tree_depth[u]    = tree_depth[v] + 1;
        dfs_on_subtree(u, v);
      }
    }

    std::vector< usize > get_indegrees() const {
      std::vector< usize > indegrees(g_size);
      for (usize v: rep(0, g_size)) {
        for (auto e: g[v]) {
          indegrees[e.to]++;
        }
      }
      return indegrees;
    }

    void construct_tree(std::vector< usize > &indegrees) {
      std::vector< usize > leaves;
      leaves.reserve(g_size);

      for (usize v: rep(0, g_size)) {
        if (indegrees[v] > 0) {
          continue;
        }
        leaves.emplace_back(v);
      }

      while (not leaves.empty()) {
        usize child = leaves.back();
        leaves.pop_back();

        usize parent = g[child][0].to;
        indegrees[parent]--;

        tree.add_undirected_edge(parent, child);

        if (indegrees[parent] == 0) {
          leaves.emplace_back(parent);
        }
      }

      for (usize v: rep(0, g_size)) {
        if (indegrees[v] == 0) {
          continue;
        }
        tree.add_undirected_edge(tree_root, v);
      }

      tree.initialize();

      for (usize v: rep(0, g_size)) {
        if (indegrees[v] == 0) {
          continue;
        }
        subtree_roots[v] = v;
        dfs_on_subtree(v, tree_root);
      }
    }

    void construct_loops(std::vector< usize > &indegrees) {
      for (usize v: rep(0, g_size)) {
        if (indegrees[v] == 0) {
          continue;
        }

        usize cur = v;
        std::vector< usize > loop;
        do {
          loop_id[cur]  = loops.size();
          loop_pos[cur] = loop.size();
          loop.emplace_back(cur);
          indegrees[cur] = 0;
          cur            = g[cur][0].to;
        } while (cur != v);

        do {
          loop_size[cur] = loop.size();
          cur            = g[cur][0].to;
        } while (cur != v);

        loops.emplace_back(std::move(loop));
      }
    }

   public:
    explicit OfflineJumpOnFunctionalGraphQuery(const graph &g_)
        : g_size(g_.size()),
          g(g_),
          tree(g_size + 1),
          tree_root(g_size),
          tree_depth(g_size),
          subtree_roots(g_size),
          loop_id(g_size),
          loop_size(g_size),
          loop_pos(g_size) {
      for (usize v: rep(0, g_size)) {
        assert(g[v].size() == 1);
      }

      std::vector< usize > indegrees = get_indegrees();
      construct_tree(indegrees);
      construct_loops(indegrees);
    }

    void add_query(usize v, u64 k) {
      qs.emplace_back(v, k);
    }

    void build() {
      OfflineLAQuery la_solver(tree);
      result.reserve(qs.size());
      for (auto [v, k]: qs) {
        if (k < tree_depth[v]) {
          la_solver.add_query(v, tree_depth[v] - k + 1);
        } else {
          query_type qi(v, k);
          k -= tree_depth[v];
          usize root       = subtree_roots[v];
          const auto &loop = loops[loop_id[root]];
          k += loop_pos[root];
          k %= loop_size[root];
          result[qi] = loop[k];
        }
      }
      la_solver.build(g_size);

      for (auto [v, k]: qs) {
        if (tree_depth[v] <= k) {
          continue;
        }
        query_type qi(v, k);
        result[qi] = la_solver.la(v, tree_depth[v] - k + 1).value();
      }
    }

    usize jump(usize v, u64 k) const {
      query_type qi(v, k);
      assert(result.count(qi));
      return result.find(qi)->second;
    }
  };
} // namespace luz

(offine) Functional Graph 上の頂点 $v$ から $k$ 回移動した先の頂点 (Offline Jump On Functional Graph) (src/graph/functional-graph/offline-query/offline-query-jump-on-functional-graph.hpp)