Submit Info #43774

Problem Lang User Status Time Memory
Cycle Detection cpp maru143 AC 145 ms 32.02 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
example_01 AC 1 ms 0.68 MiB
example_02 AC 1 ms 0.64 MiB
random_00 AC 123 ms 29.60 MiB
random_01 AC 144 ms 32.02 MiB
random_02 AC 83 ms 17.89 MiB
random_03 AC 18 ms 14.92 MiB
random_04 AC 37 ms 13.42 MiB
random_05 AC 108 ms 26.89 MiB
random_06 AC 84 ms 24.82 MiB
random_07 AC 4 ms 4.09 MiB
random_08 AC 87 ms 23.78 MiB
random_09 AC 45 ms 11.95 MiB
random_dag_00 AC 135 ms 29.30 MiB
random_dag_01 AC 145 ms 31.77 MiB
random_dag_02 AC 83 ms 17.89 MiB
random_dag_03 AC 19 ms 14.96 MiB
random_dag_04 AC 35 ms 13.42 MiB
random_dag_05 AC 123 ms 26.65 MiB
random_dag_06 AC 84 ms 24.57 MiB
random_dag_07 AC 6 ms 4.05 MiB
random_dag_08 AC 97 ms 23.66 MiB
random_dag_09 AC 50 ms 11.81 MiB
random_dag_dense_00 AC 60 ms 16.67 MiB
random_dag_dense_01 AC 58 ms 15.39 MiB
random_dag_dense_02 AC 58 ms 17.27 MiB
random_dag_dense_03 AC 59 ms 15.93 MiB
random_dag_dense_04 AC 68 ms 19.14 MiB
random_dense_00 AC 58 ms 18.02 MiB
random_dense_01 AC 59 ms 17.64 MiB
random_dense_02 AC 58 ms 18.14 MiB
random_dense_03 AC 61 ms 18.02 MiB
random_dense_04 AC 65 ms 17.52 MiB

#include <bits/stdc++.h> // #include <atcoder/all> using namespace std; using i64 = int64_t; using pii = pair<i64, i64>; #define rep(i, n) for (i64 i = 0; i < (i64)n; i++) #define per(i, n) for (i64 i = n - 1; i >= 0; i--) #define REP(i, a, b) for (i64 i = a; i < (i64)b; i++) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define fi first #define se second #ifdef LOCAL #define dbg(...) cerr<<__LINE__<<" ["<<#__VA_ARGS__<<"]:",debug(__VA_ARGS__) #else #define dbg(...) #endif template <typename T> ostream& operator<<(ostream& os, const vector<T>& vec) { for (auto& x : vec) { os << x << ' '; } return os; } template <typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& mat) { os << endl; for (auto& vec : mat) { os << vec << endl; } return os; } template <typename T1, typename T2> ostream& operator<<(ostream& os, const pair<T1, T2>& pa) { os << '(' << pa.first << ',' << pa.second << ')'; return os; } void debug() { cerr << endl; } template <typename Head, typename... Tail> void debug(Head H, Tail... T) { cerr << " " << H; debug(T...); } template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const int INF = (1 << 30) - 1; const i64 LINF = (1LL << 62) - 1; int n, m; vector<vector<pii>> G; vector<pii> edges; vector<int> used, pre; vector<int> cycle; bool dfs(int v) { used[v] = 1; for (auto [to, idx] : G[v]) { if (used[to] == 0) { pre[to] = idx; if (dfs(to)) return 1; } else if (used[to] == 1) { int now = v; while (now != to) { cycle.push_back(pre[now]); now = edges[pre[now]].fi; } cycle.push_back(idx); return 1; } } used[v] = -1; return 0; } void solve() { cin >> n >> m; G.resize(n); used.resize(n); pre.resize(n); rep(i, m) { int u, v; cin >> u >> v; G[u].push_back({ v, i }); edges.push_back({ u, v }); } rep(i, n) { if (used[i] == 0 && dfs(i)) { reverse(all(cycle)); cout << cycle.size() << endl; for (int& idx : cycle) { cout << idx << endl; } return; } } cout << -1 << endl; return; } int main() { cin.tie(0); ios::sync_with_stdio(false); solve(); return 0; }