トポロジカルソート (lib/graph/topological_sort.hpp)

• View this file on GitHub
• Last update: 2025-06-10 13:56:45+09:00
• Include: #include "lib/graph/topological_sort.hpp"

Depends on

• 重み付きグラフ (lib/graph/graph.hpp)

Verified with

• test/aoj/grl/topological_sort.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>
#include "graph/graph.hpp"

/// @brief トポロジカルソート
template <class T>
std::vector<int> topological_sort(const Graph<T> &g) {
    int n = g.size();
    std::vector<int> res;
    std::vector<bool> seen(n);
    auto dfs = [&](auto self, int v) {
        if (seen[v]) return;
        seen[v] = true;
        for (auto &e : g[v])
            if (!seen[e.to()]) self(self, e.to());
        res.emplace_back(v);
    };
    for (int i = 0; i < n; ++i) dfs(dfs, i);
    std::reverse(res.begin(), res.end());
    return res;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: graph/graph.hpp: line -1: no such header

Back to top page