cpp/graph/find_cycle.hpp

View this file on GitHub
Last update: 2024-11-03 09:29:45+09:00
Include: #include "cpp/graph/find_cycle.hpp"

Depends on

Verified with

cpp/verify/detect_cycle_directed_2.test.cpp

Code

#pragma once
#include "graph/graph_list.hpp"

/**
 * サイクルを見つける
 */
template <class Cost, class E>
vector<E> ListGraph<Cost, E>::find_cycle_directed() {
  vector<char> visited(n_, 0);
  vector<E> in(n_, {-1, -1});
  vector<E> ret;
  auto dfs = [&](auto &Self, int node) -> void {
    visited[node] = 1;
    for (auto &&e : adj[node]) {
      if (ret.size()) {
        break;
      }
      if (!visited[e.to]) {
        in[e.to] = e;
        Self(Self, e.to);
      } else if (visited[e.to] == 1) {
        ret.emplace_back(e);
        for (int v = node; v != e.to; v = in[v].from) {
          ret.emplace_back(in[v]);
        }
        reverse(ret.begin(), ret.end());
        return;
      }
    }
    visited[node] = 2;
  };
  for (int i = 0; i < n_; i++) {
    if (!visited[i]) {
      dfs(dfs, i);
    }
  }
  return ret;
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/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.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/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.12.0/x64/lib/python3.12/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/graph_list.hpp: line -1: no such header