#include <cstdio> #include <algorithm> #include <vector> #include <stack> std::vector<int> v[500005], s, odp; int w[500005], odw[500005]; int n, m, cykle, a, b; int DFS( int x ){ odw[x]=1; s.push_back(x); for( std::vector<int>::iterator it=v[x].begin(); it!=v[x].end(); it++ ){ if( !odw[*it] ){ DFS(*it); } if( odw[*it]==1 ){ cykle++; bool bul=false; for( std::vector<int>::iterator it2=s.begin(); it2!=s.end(); it2++ ){ if( *it2==*it ) bul=true; if( bul ) w[*it2]++; } } } s.pop_back(); odw[x]=2; } int main(){ scanf("%d%d", &n, &m); for( int i=1; i<=m; i++ ){ scanf("%d%d", &a, &b); v[a].push_back(b); } for( int i=1; i<=n; i++ ){ if( !odw[i] ) DFS(i); } for( int i=1; i<=n; i++ ){ if( w[i]==cykle && cykle>0 ) odp.push_back(i); } if( odp.empty() ){ printf("NIE\n"); return 0; } std::sort(odp.begin(), odp.end()); printf("%d\n", odp.size()); for( std::vector<int>::iterator it=odp.begin(); it!=odp.end(); it++ ){ printf("%d ", *it); } 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 | #include <cstdio> #include <algorithm> #include <vector> #include <stack> std::vector<int> v[500005], s, odp; int w[500005], odw[500005]; int n, m, cykle, a, b; int DFS( int x ){ odw[x]=1; s.push_back(x); for( std::vector<int>::iterator it=v[x].begin(); it!=v[x].end(); it++ ){ if( !odw[*it] ){ DFS(*it); } if( odw[*it]==1 ){ cykle++; bool bul=false; for( std::vector<int>::iterator it2=s.begin(); it2!=s.end(); it2++ ){ if( *it2==*it ) bul=true; if( bul ) w[*it2]++; } } } s.pop_back(); odw[x]=2; } int main(){ scanf("%d%d", &n, &m); for( int i=1; i<=m; i++ ){ scanf("%d%d", &a, &b); v[a].push_back(b); } for( int i=1; i<=n; i++ ){ if( !odw[i] ) DFS(i); } for( int i=1; i<=n; i++ ){ if( w[i]==cykle && cykle>0 ) odp.push_back(i); } if( odp.empty() ){ printf("NIE\n"); return 0; } std::sort(odp.begin(), odp.end()); printf("%d\n", odp.size()); for( std::vector<int>::iterator it=odp.begin(); it!=odp.end(); it++ ){ printf("%d ", *it); } printf("\n"); return 0; } |