Submit Info #38468

Problem Lang User Status Time Memory
Cycle Detection cpp tonegawa AC 148 ms 24.06 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
example_01 AC 1 ms 0.61 MiB
example_02 AC 1 ms 0.65 MiB
random_00 AC 115 ms 21.58 MiB
random_01 AC 145 ms 24.06 MiB
random_02 AC 78 ms 9.86 MiB
random_03 AC 19 ms 14.55 MiB
random_04 AC 42 ms 11.67 MiB
random_05 AC 103 ms 18.79 MiB
random_06 AC 94 ms 20.42 MiB
random_07 AC 6 ms 3.92 MiB
random_08 AC 81 ms 15.55 MiB
random_09 AC 42 ms 7.93 MiB
random_dag_00 AC 138 ms 21.17 MiB
random_dag_01 AC 148 ms 23.74 MiB
random_dag_02 AC 81 ms 9.80 MiB
random_dag_03 AC 19 ms 14.48 MiB
random_dag_04 AC 37 ms 11.55 MiB
random_dag_05 AC 125 ms 18.42 MiB
random_dag_06 AC 88 ms 20.17 MiB
random_dag_07 AC 6 ms 3.92 MiB
random_dag_08 AC 96 ms 15.30 MiB
random_dag_09 AC 48 ms 7.80 MiB
random_dag_dense_00 AC 54 ms 7.92 MiB
random_dag_dense_01 AC 53 ms 7.11 MiB
random_dag_dense_02 AC 55 ms 7.92 MiB
random_dag_dense_03 AC 55 ms 7.24 MiB
random_dag_dense_04 AC 65 ms 8.92 MiB
random_dense_00 AC 54 ms 9.42 MiB
random_dense_01 AC 55 ms 8.92 MiB
random_dense_02 AC 54 ms 8.42 MiB
random_dense_03 AC 56 ms 9.05 MiB
random_dense_04 AC 63 ms 7.67 MiB

#include <iostream> #include <string> #include <vector> #include <array> #include <queue> #include <deque> #include <algorithm> #include <set> #include <map> #include <bitset> #include <cmath> #include <functional> #include <cassert> #include <unordered_map> #include <iomanip> #define vll vector<ll> #define vvvl vector<vvl> #define vvl vector<vector<ll>> #define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c)) #define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c<b;c++) #define all(obj) (obj).begin(), (obj).end() typedef long long int ll; typedef long double ld; using namespace std; struct edge{ const int from, to, idx; edge(int f, int t, int i=-1):from(f), to(t), idx(i){} }; void cycle_detection(int now, vector<vector<edge>> &G, vector<int> &use, vector<int> &in, vector<edge*> &ans, vector<edge*> &st, edge *last){ if(!ans.empty()) return; if(in[now]){ vector<edge*> lis{last}; while(!st.empty() && st.back()->to!=now){ lis.push_back(st.back()); st.pop_back(); } reverse(lis.begin(), lis.end()); for(int i=0;i<lis.size();i++) in[lis[i]->from] = -i-1; for(int idx=0;idx<lis.size();idx++){ int v = lis[idx]->from; for(edge &e:G[v]){ if(in[e.to]>=0) continue; if(in[e.to]>in[v]){ for(int i=-in[e.to]-1;i<idx;i++) ans.push_back(lis[i]); ans.push_back(&e); return; } } } } if(use[now]) return; use[now] = in[now] = true; if(last) st.push_back(last); for(edge &e:G[now]){ if(e.to==now) continue; cycle_detection(e.to, G, use, in, ans, st, &e); } in[now] = false; if(!st.empty()) st.pop_back(); } vector<edge*> cycle_detection(vector<vector<edge>> &G){ int n = G.size(); vector<int> use(n, 0), in(n, 0); vector<edge*> ans, st; for(int i=0;i<n;i++){ if(!ans.empty()) break; if(use[i]) continue; cycle_detection(i, G, use, in, ans, st, nullptr); } return ans; } int main(){ int n, m;scanf("%d %d", &n, &m); vector<vector<edge>> G(n); for(int i=0;i<m;i++){ int a, b;scanf("%d %d", &a, &b); G[a].push_back(edge(a, b, i)); } auto ans = cycle_detection(G); if(ans.empty()) printf("%d\n", -1); else{ printf("%d\n", int(ans.size())); for(int i=0;i<ans.size();i++) printf("%d\n", ans[i]->idx); } }