#include <cstdio> #include <vector> using namespace std; const int MAXN=(int)1e6+5; vector <int> G[MAXN]; int used[MAXN],res[MAXN],wywa[MAXN]; int n,m,a,b,pos,cykl,cykle; void dfs(int x) { if(wywa[x]==0) { used[x]=1; if(cykl==0) { int s=G[x].size(); for(int i=0; i<s; ++i) { if(used[G[x][i]]==0) { dfs(G[x][i]); } else if(used[G[x][i]]==1) { cykl=1; } } } used[x]=2; } } int main() { scanf("%d%d", &n, &m); for(int i=0; i<m; ++i) { scanf("%d%d", &a, &b); G[a].push_back(b); } for(int i=1; i<=n; ++i) { if(!used[i]) { cykl=0; dfs(i); if(cykl==1) ++cykle; } } if(cykle==0) { printf("NIE"); return 0; } else if(cykle>1) { printf("0\n"); return 0; } for(int j=1; j<=n; ++j) used[j]=0; for(int i=1; i<=n; ++i) { cykl=0; wywa[i]=1; for(int j=1; j<=n; ++j) { if(used[j]==0) { dfs(j); if(cykl==1) break; } } if(cykl==0) res[pos++]=i; for(int j=1; j<=n; ++j) used[j]=0; wywa[i]=0; } printf("%d\n", pos); for(int i=0; i<pos; ++i) printf("%d ", res[i]); }
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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | #include <cstdio> #include <vector> using namespace std; const int MAXN=(int)1e6+5; vector <int> G[MAXN]; int used[MAXN],res[MAXN],wywa[MAXN]; int n,m,a,b,pos,cykl,cykle; void dfs(int x) { if(wywa[x]==0) { used[x]=1; if(cykl==0) { int s=G[x].size(); for(int i=0; i<s; ++i) { if(used[G[x][i]]==0) { dfs(G[x][i]); } else if(used[G[x][i]]==1) { cykl=1; } } } used[x]=2; } } int main() { scanf("%d%d", &n, &m); for(int i=0; i<m; ++i) { scanf("%d%d", &a, &b); G[a].push_back(b); } for(int i=1; i<=n; ++i) { if(!used[i]) { cykl=0; dfs(i); if(cykl==1) ++cykle; } } if(cykle==0) { printf("NIE"); return 0; } else if(cykle>1) { printf("0\n"); return 0; } for(int j=1; j<=n; ++j) used[j]=0; for(int i=1; i<=n; ++i) { cykl=0; wywa[i]=1; for(int j=1; j<=n; ++j) { if(used[j]==0) { dfs(j); if(cykl==1) break; } } if(cykl==0) res[pos++]=i; for(int j=1; j<=n; ++j) used[j]=0; wywa[i]=0; } printf("%d\n", pos); for(int i=0; i<pos; ++i) printf("%d ", res[i]); } |