Submit Info #50872

Problem Lang User Status Time Memory
Cycle Detection cpp cyx0406 AC 135 ms 25.34 MiB

ケース詳細
Name Status Time Memory
example_00 AC 7 ms 12.09 MiB
example_01 AC 7 ms 12.09 MiB
example_02 AC 7 ms 12.09 MiB
random_00 AC 101 ms 24.22 MiB
random_01 AC 135 ms 25.34 MiB
random_02 AC 57 ms 17.97 MiB
random_03 AC 19 ms 16.84 MiB
random_04 AC 34 ms 17.34 MiB
random_05 AC 92 ms 22.59 MiB
random_06 AC 82 ms 22.21 MiB
random_07 AC 11 ms 13.34 MiB
random_08 AC 71 ms 20.71 MiB
random_09 AC 32 ms 16.46 MiB
random_dag_00 AC 112 ms 23.70 MiB
random_dag_01 AC 125 ms 24.84 MiB
random_dag_02 AC 51 ms 17.97 MiB
random_dag_03 AC 19 ms 16.84 MiB
random_dag_04 AC 31 ms 17.21 MiB
random_dag_05 AC 116 ms 22.34 MiB
random_dag_06 AC 71 ms 21.96 MiB
random_dag_07 AC 10 ms 13.33 MiB
random_dag_08 AC 83 ms 20.46 MiB
random_dag_09 AC 37 ms 16.46 MiB
random_dag_dense_00 AC 22 ms 17.21 MiB
random_dag_dense_01 AC 23 ms 16.58 MiB
random_dag_dense_02 AC 20 ms 16.96 MiB
random_dag_dense_03 AC 23 ms 16.71 MiB
random_dag_dense_04 AC 24 ms 17.59 MiB
random_dense_00 AC 22 ms 18.21 MiB
random_dense_01 AC 22 ms 17.58 MiB
random_dense_02 AC 19 ms 17.34 MiB
random_dense_03 AC 25 ms 17.70 MiB
random_dense_04 AC 24 ms 16.72 MiB

#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; template <class T> inline void read(T &x) { static char ch; while (!isdigit(ch = getchar())); x = ch - '0'; while (isdigit(ch = getchar())) x = x * 10 + ch - '0'; } const int MaxN = 500000 + 5; const int MaxE = 500000 + 5; int n, m; vector<pii> adj[MaxN]; pii pre[MaxN]; bool ins[MaxN], vis[MaxN]; void dfs(int u) { vis[u] = ins[u] = true; for (pii e : adj[u]) { int v = e.first; if (!vis[v]) { pre[v] = make_pair(u, e.second); dfs(v); } else if (ins[v]) { vector<int> res(1, e.second); for (int x = u; x != v; x = pre[x].first) res.push_back(pre[x].second); reverse(res.begin(), res.end()); printf("%d\n", (int)res.size()); for (int x : res) printf("%d\n", x); exit(0); } } ins[u] = false; } int main() { read(n), read(m); for (int i = 0; i < m; ++i) { int u, v; read(u), read(v); adj[u].emplace_back(v, i); } for (int i = 0; i < n; ++i) { if (!vis[i]) dfs(i); } puts("-1"); return 0; }