Submit Info #42099

Problem Lang User Status Time Memory
Cycle Detection cpp (anonymous) AC 161 ms 25.86 MiB

ケース詳細
Name Status Time Memory
example_00 AC 8 ms 12.55 MiB
example_01 AC 8 ms 12.55 MiB
example_02 AC 8 ms 12.55 MiB
random_00 AC 122 ms 25.04 MiB
random_01 AC 161 ms 25.86 MiB
random_02 AC 79 ms 19.05 MiB
random_03 AC 21 ms 15.17 MiB
random_04 AC 43 ms 16.98 MiB
random_05 AC 117 ms 23.90 MiB
random_06 AC 104 ms 21.80 MiB
random_07 AC 13 ms 13.42 MiB
random_08 AC 92 ms 21.67 MiB
random_09 AC 49 ms 17.30 MiB
random_dag_00 AC 156 ms 24.30 MiB
random_dag_01 AC 158 ms 25.17 MiB
random_dag_02 AC 83 ms 18.92 MiB
random_dag_03 AC 21 ms 15.17 MiB
random_dag_04 AC 44 ms 16.80 MiB
random_dag_05 AC 145 ms 23.17 MiB
random_dag_06 AC 92 ms 21.48 MiB
random_dag_07 AC 12 ms 13.42 MiB
random_dag_08 AC 112 ms 21.05 MiB
random_dag_09 AC 55 ms 17.05 MiB
random_dag_dense_00 AC 54 ms 18.48 MiB
random_dag_dense_01 AC 56 ms 18.05 MiB
random_dag_dense_02 AC 54 ms 18.74 MiB
random_dag_dense_03 AC 57 ms 18.24 MiB
random_dag_dense_04 AC 63 ms 19.42 MiB
random_dense_00 AC 53 ms 18.80 MiB
random_dense_01 AC 55 ms 18.80 MiB
random_dense_02 AC 53 ms 18.92 MiB
random_dense_03 AC 53 ms 18.87 MiB
random_dense_04 AC 60 ms 18.80 MiB

#include <bits/stdc++.h> using namespace std; #define FOR(i,n) for (int i=0;i<(n);++i) typedef vector<int> vi; typedef pair<int,int> ii; typedef vector<ii> vii; typedef vector<vi> vvi; #define MP make_pair typedef long long ll; void READ(bool _local){ ios_base::sync_with_stdio(false); cin.tie(0); #ifdef _DEBUG if (_local) freopen ("in.txt", "r", stdin); #endif } const int N=5E5; int n,m; vi g[N]; ii edges[N]; int p[N]; bool vis[N]; void dfs(int node){ vis[node]=1; for(int i:g[node]){ if (edges[i].second==node){ cout << 1 << '\n' << i; exit(0); } if (p[edges[i].second]==-1) { if (vis[edges[i].second]) continue; p[node]=i; dfs(edges[i].second); } else{ vi ret; int u = edges[i].second; while(u!=node){ ret.push_back(p[u]); u = edges[p[u]].second; } ret.push_back(i); cout << ret.size() << '\n'; for(int j:ret) cout << j << '\n'; exit(0); } } p[node]=-1; } int main(){ READ(0); cin>>n>>m; FOR(i,m){ cin>>edges[i].first>>edges[i].second; g[edges[i].first].push_back(i); } memset(p,-1,n*sizeof(int)); memset(vis,0,sizeof(vis)); FOR(i,n){ if (!vis[i]) dfs(i); } cout << -1 << '\n'; }