Submit Info #31999

Problem Lang User Status Time Memory
Cycle Detection cpp piddy AC 173 ms 24.42 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
example_01 AC 1 ms 0.69 MiB
example_02 AC 1 ms 0.64 MiB
random_00 AC 99 ms 22.62 MiB
random_01 AC 118 ms 24.30 MiB
random_02 AC 76 ms 16.12 MiB
random_03 AC 17 ms 11.43 MiB
random_04 AC 36 ms 10.17 MiB
random_05 AC 94 ms 20.92 MiB
random_06 AC 99 ms 18.49 MiB
random_07 AC 6 ms 3.17 MiB
random_08 AC 72 ms 16.74 MiB
random_09 AC 45 ms 9.67 MiB
random_dag_00 AC 171 ms 22.80 MiB
random_dag_01 AC 173 ms 24.42 MiB
random_dag_02 AC 91 ms 16.05 MiB
random_dag_03 AC 21 ms 11.42 MiB
random_dag_04 AC 45 ms 10.15 MiB
random_dag_05 AC 151 ms 20.92 MiB
random_dag_06 AC 86 ms 18.55 MiB
random_dag_07 AC 5 ms 3.24 MiB
random_dag_08 AC 100 ms 16.80 MiB
random_dag_09 AC 54 ms 9.55 MiB
random_dag_dense_00 AC 59 ms 14.42 MiB
random_dag_dense_01 AC 56 ms 13.18 MiB
random_dag_dense_02 AC 55 ms 13.75 MiB
random_dag_dense_03 AC 56 ms 13.56 MiB
random_dag_dense_04 AC 61 ms 15.92 MiB
random_dense_00 AC 57 ms 16.42 MiB
random_dense_01 AC 54 ms 16.11 MiB
random_dense_02 AC 53 ms 15.73 MiB
random_dense_03 AC 60 ms 16.17 MiB
random_dense_04 AC 67 ms 14.55 MiB

#include <iostream> #include <vector> struct edge { std::uint_fast32_t from, to; std::int_fast64_t weight; edge() = default; edge(const std::uint_fast32_t& from_, const std::uint_fast32_t& to_, const std::int_fast64_t& weight_) : from(from_), to(to_), weight(weight_) {} bool operator<(const edge& rhs) const {return weight < rhs.weight;} }; class adjacency_list { std::vector<std::vector<edge>> v; public : adjacency_list(const std::uint_fast32_t& node_size) : v(node_size) {} void add_edge(const std::uint_fast32_t& from, const std::uint_fast32_t& to, const std::int_fast64_t& weight = 1) { v[from].emplace_back(from, to, weight); } std::uint_fast32_t size() const {return v.size();} const std::vector<edge>& operator[](const std::uint_fast32_t& k) const {return v[k];} }; std::vector<bool> visited, visited2; std::vector<std::pair<int, int>> v; void dfs(const int& now, const adjacency_list& G) { if (visited[now]) { int idx; for (int i = 0; i < v.size(); i++) { if (v[i].first == now) { idx = i; break; } } std::cout << v.size() - idx << '\n'; for (int i = idx; i < v.size(); i++) std::cout << v[i].second << '\n'; exit(0); } visited[now] = visited2[now] = true; for (auto e : G[now]) { if (visited2[e.to] && !visited[e.to]) continue; v.emplace_back(now, e.weight); dfs(e.to, G); v.pop_back(); } visited[now] = false; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N, M; std::cin >> N >> M; adjacency_list G(N); for (int i = 0; i < M; i++) { int u, v; std::cin >> u >> v; G.add_edge(u, v, i); } visited.resize(N, false); visited2.resize(N, false); for (int i = 0; i < N; i++) if (!visited2[i]) dfs(i, G); std::cout << -1 << '\n'; }