#include<cstdio> #include<vector> using namespace std; const int MN=(int)5e5+5; int n, m, czycykl=0, odw[MN], zly, t=1, akt[MN]; vector<int> sas[MN], wyn; void dfs(int v){ odw[v]=t; akt[v]=1; for(int i=0; i<sas[v].size() && czycykl==0; i++){ int v2=sas[v][i]; if(akt[v2]==1) czycykl=1; else{ if(odw[v2]<t && v2!=zly) dfs(v2); } } akt[v]=0; } int main(){ int i, j, a, b; scanf("%d%d", &n, &m); for(i=0; i<m; i++){ scanf("%d%d", &a, &b); sas[a].push_back(b); } for(i=1; i<=n; i++) sas[0].push_back(i); zly=n+1; czycykl=0; dfs(0); if(czycykl==0){ printf("NIE\n"); return 0; } for(i=1; i<=n; i++){ t++; zly=i; czycykl=0; dfs(0); if(czycykl==0){ wyn.push_back(i); } } printf("%d\n", wyn.size()); for(i=0; i<wyn.size(); i++) printf("%d ", wyn[i]); printf("\n"); 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 | #include<cstdio> #include<vector> using namespace std; const int MN=(int)5e5+5; int n, m, czycykl=0, odw[MN], zly, t=1, akt[MN]; vector<int> sas[MN], wyn; void dfs(int v){ odw[v]=t; akt[v]=1; for(int i=0; i<sas[v].size() && czycykl==0; i++){ int v2=sas[v][i]; if(akt[v2]==1) czycykl=1; else{ if(odw[v2]<t && v2!=zly) dfs(v2); } } akt[v]=0; } int main(){ int i, j, a, b; scanf("%d%d", &n, &m); for(i=0; i<m; i++){ scanf("%d%d", &a, &b); sas[a].push_back(b); } for(i=1; i<=n; i++) sas[0].push_back(i); zly=n+1; czycykl=0; dfs(0); if(czycykl==0){ printf("NIE\n"); return 0; } for(i=1; i<=n; i++){ t++; zly=i; czycykl=0; dfs(0); if(czycykl==0){ wyn.push_back(i); } } printf("%d\n", wyn.size()); for(i=0; i<wyn.size(); i++) printf("%d ", wyn[i]); printf("\n"); return 0; } |