C++ Library for Competitive Programming
/*
* @title グラフ/有向非巡回グラフ上の到達可能性判定
*
* verification-helper: IGNORE
* verification-helper: PROBLEM https://atcoder.jp/contests/typical90/tasks/typical90_bg
*/
#include <iostream>
#include <vector>
#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/reachability_on_dag.hpp"
int main() {
int n, m, q;
std::cin >> n >> m >> q;
std::vector<std::vector<emthrm::Edge<bool>>> graph(n);
while (m--) {
int x, y;
std::cin >> x >> y;
--x; --y;
graph[x].emplace_back(x, y);
}
std::vector<int> a(q), b(q);
for (int i = 0; i < q; ++i) {
std::cin >> a[i] >> b[i];
--a[i]; --b[i];
}
for (const bool ans : emthrm::reachability_on_dag(graph, a, b)) {
std::cout << (ans ? "Yes\n" : "No\n");
}
return 0;
}
#line 1 "test/graph/reachability_on_dag.test.cpp"
/*
* @title グラフ/有向非巡回グラフ上の到達可能性判定
*
* verification-helper: IGNORE
* verification-helper: PROBLEM https://atcoder.jp/contests/typical90/tasks/typical90_bg
*/
#include <iostream>
#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/reachability_on_dag.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <utility>
#line 10 "include/emthrm/graph/reachability_on_dag.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 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
#line 13 "test/graph/reachability_on_dag.test.cpp"
int main() {
int n, m, q;
std::cin >> n >> m >> q;
std::vector<std::vector<emthrm::Edge<bool>>> graph(n);
while (m--) {
int x, y;
std::cin >> x >> y;
--x; --y;
graph[x].emplace_back(x, y);
}
std::vector<int> a(q), b(q);
for (int i = 0; i < q; ++i) {
std::cin >> a[i] >> b[i];
--a[i]; --b[i];
}
for (const bool ans : emthrm::reachability_on_dag(graph, a, b)) {
std::cout << (ans ? "Yes\n" : "No\n");
}
return 0;
}