#include<bits/stdc++.h> using namespace std; vector<int>v[500007]; bool odw[500007]; bool odp[500007]; bool jestem[500007]; int N,M; bool jestcykl = false; void dfs(int a,int be) { odw[a] = true; jestem[a] = true; for (int i = 0;i < v[a].size();i++) { if (v[a][i] == be) { jestcykl = true; for (int w = 1;w <= N;w++) { if (!jestem[w]) odp[w] = false; } } else if (!odw[v[a][i]]) dfs(v[a][i],be); } jestem[a] = false; odw[a] = false; } int main() { scanf("%d%d",&N,&M); int a,b; for (int i = 0;i < M;i++) { scanf("%d%d",&a,&b); v[a].push_back(b); } for (int i = 1;i <= N;i++) odp[i] = true; for (int i = 1;i <= N;i++) dfs(i,i); int il = 0; for (int i = 1;i <= N;i++) if (odp[i]) il++; if (!jestcykl) { printf("NIE\n"); return 0; } printf("%d\n",il); for (int i = 1;i <= N;i++) if (odp[i]) printf("%d ",i); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include<bits/stdc++.h> using namespace std; vector<int>v[500007]; bool odw[500007]; bool odp[500007]; bool jestem[500007]; int N,M; bool jestcykl = false; void dfs(int a,int be) { odw[a] = true; jestem[a] = true; for (int i = 0;i < v[a].size();i++) { if (v[a][i] == be) { jestcykl = true; for (int w = 1;w <= N;w++) { if (!jestem[w]) odp[w] = false; } } else if (!odw[v[a][i]]) dfs(v[a][i],be); } jestem[a] = false; odw[a] = false; } int main() { scanf("%d%d",&N,&M); int a,b; for (int i = 0;i < M;i++) { scanf("%d%d",&a,&b); v[a].push_back(b); } for (int i = 1;i <= N;i++) odp[i] = true; for (int i = 1;i <= N;i++) dfs(i,i); int il = 0; for (int i = 1;i <= N;i++) if (odp[i]) il++; if (!jestcykl) { printf("NIE\n"); return 0; } printf("%d\n",il); for (int i = 1;i <= N;i++) if (odp[i]) printf("%d ",i); return 0; } |