graph/topological-sort.hpp

• View this file on GitHub
• Last update: 1970-01-01 00:00:00+00:00
• Include: #include "graph/topological-sort.hpp"

Code

#pragma once

#include "./base.hpp"
#include "./graph-type.hpp"

#include <queue>

namespace matumoto {
  // if graph is not DAG, return {}
  vector<int> topological_sort(const UnWeightedGraph &graph) {
    int n = graph.size();
    vector<int> in_degree(n, 0);

    auto edges = graph.edges();
    for (auto e: edges) {
      in_degree[e.to()]++;
    }

    vector<UnWeightedEdges> adj_list = graph.graph();

    queue<int> q;
    for (int i = 0; i < n; i++) {
      if (in_degree[i] == 0)
        q.push(i);
    }

    vector<int> sorted_indexes;
    while (not q.empty()) {
      int v = q.front();
      q.pop();

      sorted_indexes.emplace_back(v);
      for (auto e: adj_list[v]) {
        int to = e.to();

        in_degree[to]--;
        if (in_degree[to] == 0)
          q.push(to);
      }
    }

    bool has_cycle = int(sorted_indexes.size()) < n;
    if (has_cycle) {
      return {};
    }
    return sorted_indexes;
  }
} // namespace matumoto

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: graph-type.hpp: line -1: no such header

Back to top page