C++ Library for Competitive Programming
#include "emthrm/graph/topological_sort.hpp"
有向非巡回グラフ (directed acyclic graph) のトポロジカル順序を求めるアルゴリズムである。
$i$ 番目の頂点 $V_i$ に対して辺 $(V_i, V_j)$ が存在するならば $i < j$ を満たすような頂点の番号の付け方である。
$O(\lvert V \rvert + \lvert E \rvert)$
名前 | 戻り値 |
---|---|
template <typename CostType> std::vector<int> topological_sort(const std::vector<std::vector<Edge<CostType>>>& graph);
|
グラフ $\mathrm{graph}$ のトポロジカル順序。ただし存在しないときは空配列を返す。 |
Kahn’s algorithm
#ifndef EMTHRM_GRAPH_TOPOLOGICAL_SORT_HPP_
#define EMTHRM_GRAPH_TOPOLOGICAL_SORT_HPP_
#include <queue>
#include <ranges>
#include <utility>
#include <vector>
#include "emthrm/graph/edge.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
#endif // EMTHRM_GRAPH_TOPOLOGICAL_SORT_HPP_
#line 1 "include/emthrm/graph/topological_sort.hpp"
#include <queue>
#include <ranges>
#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 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