有向非巡回グラフ上の到達可能性判定
(include/emthrm/graph/reachability_on_dag.hpp)

• View this file on GitHub
• Last update: 2023-02-24 21:17:22+09:00
• Include: #include "emthrm/graph/reachability_on_dag.hpp"

時間計算量

ワードサイズを $W$ とおくと $O\left(\frac{Q(\lvert V \rvert + \lvert E \rvert)}{W} \right)$

仕様

名前	戻り値
template <typename CostType> std::vector<bool> reachability_on_dag(const std::vector<std::vector<Edge<CostType>>>& graph, const std::vector<int>& ss, const std::vector<int>& ts);	有向非巡回グラフ $\mathrm{graph}$ 上で頂点 $\mathrm{ss}_i$ から頂点 $\mathrm{ts}_i$ に到達できるか。

参考文献

• https://ei1333.github.io/library/graph/others/offline-dag-reachability.hpp

Submissons

https://atcoder.jp/contests/typical90/submissions/25153847

Depends on

• 辺 (include/emthrm/graph/edge.hpp)
• トポロジカルソート (topological sort) (include/emthrm/graph/topological_sort.hpp)

Verified with

• グラフ/有向非巡回グラフ上の到達可能性判定 (test/graph/reachability_on_dag.test.cpp)

Code

#ifndef EMTHRM_GRAPH_REACHABILITY_ON_DAG_HPP_
#define EMTHRM_GRAPH_REACHABILITY_ON_DAG_HPP_

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>

#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/topological_sort.hpp"

namespace emthrm {

template <typename CostType>
std::vector<bool> reachability_on_dag(
    const std::vector<std::vector<Edge<CostType>>>& graph,
    const std::vector<int>& ss, const std::vector<int>& ts) {
  const int n = graph.size(), q = ss.size();
  assert(std::cmp_equal(ts.size(), q));
  const std::vector<int> order = topological_sort(graph);
  std::vector<bool> can_reach(q, false);
  std::vector<std::uint64_t> dp(n, 0);
  for (int i = 0; i < q;) {
    const int j = std::min(i + std::numeric_limits<std::uint64_t>::digits, q);
    std::fill(dp.begin(), dp.end(), 0);
    for (int k = i; k < j; ++k) {
      dp[ss[k]] |= UINT64_C(1) << (k - i);
    }
    for (const int node : order) {
      for (const int e : graph[node]
                       | std::views::transform(&Edge<CostType>::dst)) {
        dp[e] |= dp[node];
      }
    }
    for (int k = i; k < j; ++k) {
      can_reach[k] = dp[ts[k]] >> (k - i) & 1;
    }
    i = j;
  }
  return can_reach;
}

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_REACHABILITY_ON_DAG_HPP_

#line 1 "include/emthrm/graph/reachability_on_dag.hpp"



#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/graph/topological_sort.hpp"



#include <queue>
#include <ranges>
#line 8 "include/emthrm/graph/topological_sort.hpp"

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 10 "include/emthrm/graph/topological_sort.hpp"

namespace emthrm {

template <typename CostType>
std::vector<int> topological_sort(
    const std::vector<std::vector<Edge<CostType>>>& graph) {
  const int n = graph.size();
  std::vector<int> deg(n, 0);
  for (const int e : graph
                   | std::views::join
                   | std::views::transform(&Edge<CostType>::dst)) {
    ++deg[e];
  }
  std::queue<int> que;
  for (int i = 0; i < n; ++i) {
    if (deg[i] == 0) que.emplace(i);
  }
  std::vector<int> res;
  res.reserve(n);
  while (!que.empty()) {
    const int ver = que.front();
    que.pop();
    res.emplace_back(ver);
    for (const int e : graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (--deg[e] == 0) que.emplace(e);
    }
  }
  return std::cmp_equal(res.size(), n) ? res : std::vector<int>{};
}

}  // namespace emthrm


#line 13 "include/emthrm/graph/reachability_on_dag.hpp"

namespace emthrm {

template <typename CostType>
std::vector<bool> reachability_on_dag(
    const std::vector<std::vector<Edge<CostType>>>& graph,
    const std::vector<int>& ss, const std::vector<int>& ts) {
  const int n = graph.size(), q = ss.size();
  assert(std::cmp_equal(ts.size(), q));
  const std::vector<int> order = topological_sort(graph);
  std::vector<bool> can_reach(q, false);
  std::vector<std::uint64_t> dp(n, 0);
  for (int i = 0; i < q;) {
    const int j = std::min(i + std::numeric_limits<std::uint64_t>::digits, q);
    std::fill(dp.begin(), dp.end(), 0);
    for (int k = i; k < j; ++k) {
      dp[ss[k]] |= UINT64_C(1) << (k - i);
    }
    for (const int node : order) {
      for (const int e : graph[node]
                       | std::views::transform(&Edge<CostType>::dst)) {
        dp[e] |= dp[node];
      }
    }
    for (int k = i; k < j; ++k) {
      can_reach[k] = dp[ts[k]] >> (k - i) & 1;
    }
    i = j;
  }
  return can_reach;
}

}  // namespace emthrm

Back to top page