Submit Info #59499

Problem Lang User Status Time Memory
Cycle Detection cpp-acl suisen AC 571 ms 46.74 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
example_01 AC 1 ms 0.42 MiB
example_02 AC 1 ms 0.45 MiB
random_00 AC 507 ms 44.06 MiB
random_01 AC 541 ms 46.74 MiB
random_02 AC 361 ms 29.18 MiB
random_03 AC 29 ms 14.59 MiB
random_04 AC 92 ms 16.60 MiB
random_05 AC 484 ms 40.81 MiB
random_06 AC 275 ms 33.10 MiB
random_07 AC 12 ms 4.01 MiB
random_08 AC 343 ms 32.54 MiB
random_09 AC 171 ms 18.12 MiB
random_dag_00 AC 571 ms 43.34 MiB
random_dag_01 AC 502 ms 46.02 MiB
random_dag_02 AC 402 ms 28.79 MiB
random_dag_03 AC 29 ms 14.58 MiB
random_dag_04 AC 92 ms 16.47 MiB
random_dag_05 AC 476 ms 39.99 MiB
random_dag_06 AC 298 ms 32.75 MiB
random_dag_07 AC 10 ms 4.01 MiB
random_dag_08 AC 374 ms 31.91 MiB
random_dag_09 AC 196 ms 17.73 MiB
random_dag_dense_00 AC 273 ms 14.90 MiB
random_dag_dense_01 AC 166 ms 3.88 MiB
random_dag_dense_02 AC 144 ms 3.09 MiB
random_dag_dense_03 AC 165 ms 3.78 MiB
random_dag_dense_04 AC 297 ms 11.50 MiB
random_dense_00 AC 315 ms 20.27 MiB
random_dense_01 AC 184 ms 5.83 MiB
random_dense_02 AC 148 ms 3.64 MiB
random_dense_03 AC 182 ms 5.69 MiB
random_dense_04 AC 333 ms 16.94 MiB

#define PROBLEM "https://judge.yosupo.jp/problem/cycle_detection" #include <iostream> #include <map> #include <deque> #include <optional> #include <vector> namespace suisen { std::optional<std::vector<int>> cycle_detection(const std::vector<std::vector<int>> &g, bool directed) { const int n = g.size(); std::vector<int> index(n, -1); std::vector<int> cycle; bool found = false; std::vector<char> vis(n, false); int t = 0; auto dfs = [&](auto self, int u, int p) -> void { index[u] = cycle.size(); cycle.push_back(u); vis[u] = true; for (int v : g[u]) { if (not directed and v == p) continue; if (index[v] >= 0) { found = true; cycle.erase(cycle.begin(), cycle.begin() + index[v]); } else if (not vis[v]) { self(self, v, u); } if (found) break; } if (not found) { cycle.pop_back(); index[u] = -1; } }; for (int i = 0; i < n; ++i) { if (vis[i]) continue; dfs(dfs, i, -1); if (found) return std::make_optional(cycle); ++t; } return std::nullopt; } } // namespace suisen int main() { int n, m; std::cin >> n >> m; std::vector<std::vector<int>> g(n); std::map<std::pair<int, int>, int> edge_id; for (int i = 0; i < m; ++i) { int u, v; std::cin >> u >> v; edge_id[{u, v}] = i; g[u].push_back(v); } const auto optional_cycle = suisen::cycle_detection(g, /* directed = */true); if (optional_cycle.has_value()) { const auto &cycle = *optional_cycle; const int sz = cycle.size(); std::cout << sz << '\n'; for (int i = 0; i < sz; ++i) { const int u = cycle[i], v = cycle[(i + 1) % sz]; std::cout << edge_id[{u, v}] << '\n'; } } else { std::cout << -1 << '\n'; } return 0; }