Submit Info #52444

Problem Lang User Status Time Memory
Cycle Detection cpp shiomusubi496 AC 553 ms 46.59 MiB

ケース詳細
Name Status Time Memory
example_00 AC 7 ms 12.10 MiB
example_01 AC 7 ms 12.10 MiB
example_02 AC 6 ms 12.10 MiB
random_00 AC 488 ms 45.84 MiB
random_01 AC 553 ms 46.59 MiB
random_02 AC 389 ms 39.58 MiB
random_03 AC 32 ms 15.21 MiB
random_04 AC 99 ms 21.21 MiB
random_05 AC 483 ms 44.46 MiB
random_06 AC 289 ms 33.08 MiB
random_07 AC 16 ms 13.34 MiB
random_08 AC 382 ms 37.35 MiB
random_09 AC 197 ms 27.09 MiB
random_dag_00 AC 538 ms 44.72 MiB
random_dag_01 AC 546 ms 45.84 MiB
random_dag_02 AC 408 ms 39.09 MiB
random_dag_03 AC 36 ms 15.21 MiB
random_dag_04 AC 111 ms 21.09 MiB
random_dag_05 AC 493 ms 43.59 MiB
random_dag_06 AC 280 ms 32.70 MiB
random_dag_07 AC 16 ms 13.34 MiB
random_dag_08 AC 384 ms 36.71 MiB
random_dag_09 AC 191 ms 26.84 MiB
random_dag_dense_00 AC 272 ms 26.59 MiB
random_dag_dense_01 AC 170 ms 15.71 MiB
random_dag_dense_02 AC 149 ms 14.84 MiB
random_dag_dense_03 AC 174 ms 15.59 MiB
random_dag_dense_04 AC 292 ms 23.21 MiB
random_dense_00 AC 343 ms 31.97 MiB
random_dense_01 AC 192 ms 17.47 MiB
random_dense_02 AC 155 ms 15.33 MiB
random_dense_03 AC 198 ms 17.47 MiB
random_dense_04 AC 355 ms 28.59 MiB

#include<bits/stdc++.h> using namespace std; int N,M; bool used[500000]; bool used2[500000]; vector<int> G[500000]; vector<int> ans; map<pair<int,int>,int>edge; void dfs(int v,int p){ used2[v]=true; used[v]=true; ans.push_back(v); for(int t:G[v])if(t!=p){ if(used[t]){ ans.erase(ans.begin(),find(ans.begin(),ans.end(),t)); cout<<ans.size()<<endl; ans.push_back(t); for(int i=0;i<ans.size()-1;i++)cout<<edge[{ans[i],ans[i+1]}]<<endl; exit(0); } if(used2[t])continue; dfs(t,v); } ans.pop_back(); used[v]=false; } int main(){ int N,M; cin>>N>>M; for(int i=0;i<M;i++){ int a,b; cin>>a>>b; G[a].push_back(b); edge[{a,b}]=i; } fill(used,used+N,false); fill(used2,used2+N,false); for(int i=0;i<N;i++){ if(!used2[i])dfs(i,-1); } puts("-1"); }