This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/cycle_detection #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../graph/cycle.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,m; cin>>n>>m; DirectedCycle G(n); vector<map<int, int>> I(n); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; G.add_edge(u,v); I[u][v]=i; } auto vs=G.build(); if(vs.empty()){ cout<<-1<<endl; return 0; } int l=vs.size(); cout<<l<<endl; for(int i=0;i<l;i++) cout<<I[vs[i]][vs[(i+1)%l]]<<'\n'; return 0; }
#line 1 "test/yosupo/cycle_detection.test.cpp" // verification-helper: PROBLEM https://judge.yosupo.jp/problem/cycle_detection #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "graph/cycle.cpp" #line 3 "graph/cycle.cpp" using namespace std; #endif //BEGIN CUT HERE template<bool directed> struct Cycle{ vector<int> used; vector<vector<int>> G; Cycle(int n_):used(n_,0),G(n_){} void add_edge(int u,int v){ G[u].emplace_back(v); if(not directed) G[v].emplace_back(u); } vector<int> vs; int dfs(int v,int p){ used[v]=1; vs.emplace_back(v); for(int u:G[v]){ if((not directed) and u==p) continue; if(used[u]==2) continue; if(used[u]==1) return u; int res=dfs(u,v); if(~res) return res; } used[v]=2; vs.pop_back(); return -1; } vector<int> build(){ for(int i=0;i<(int)G.size();i++){ if(used[i]) continue; int start=dfs(i,-1); if(start<0) continue; vs.erase(vs.begin(),find(vs.begin(),vs.end(),start)); return vs; } return {}; } }; using DirectedCycle = Cycle<true>; using UndirectedCycle = Cycle<false>; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 8 "test/yosupo/cycle_detection.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,m; cin>>n>>m; DirectedCycle G(n); vector<map<int, int>> I(n); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; G.add_edge(u,v); I[u][v]=i; } auto vs=G.build(); if(vs.empty()){ cout<<-1<<endl; return 0; } int l=vs.size(); cout<<l<<endl; for(int i=0;i<l;i++) cout<<I[vs[i]][vs[(i+1)%l]]<<'\n'; return 0; }