#include <iostream> #include <vector> #include <set> using namespace std; int odwiedzony[500000] = {0}; int ile_cykli = 0; bool nongrata[500000]; vector<int> out[500000]; vector<int> in[500000]; int ilein[500000]; int ileout[500000]; void usunin(int s){ nongrata[s] = true; vector<int>::iterator it; for(it = out[s].begin(); it != out[s].end(); it++){ if(!nongrata[*it]){ ilein[*it]--; if(ilein[*it] == 0) usunin(*it); } } } void usunout(int s){ nongrata[s] = true; vector<int>::iterator it; for(it = in[s].begin(); it != in[s].end(); it++){ if(!nongrata[*it]){ ileout[*it]--; if(ileout[*it] == 0) usunout(*it); } } } void przejdz_graf(int s){ if(odwiedzony[s] > 0){ odwiedzony[s]++; ile_cykli++; } if(odwiedzony[s] == 0){ vector<int>::iterator it; for(it = out[s].begin(); it != out[s].end(); it++){ if(!nongrata[s]){ odwiedzony[s]++; przejdz_graf(*it); } } } } int main(){ int n,m; cin>>n>>m; int a,b; for(int i = 0; i < m; i++){ cin>>a>>b; out[a-1].push_back(b-1); in[b-1].push_back(a-1); } for(int i = 0; i < n; i++){ ilein[i] = in[i].size(); ileout[i] = out[i].size(); } for(int i = 0; i < n; i++){ if(!nongrata[i]){ if(ilein[i] == 0) usunin(i); if(ileout[i] == 0) usunout(i); } } int j = 0; while(j < n && nongrata[j]) j++; if(j == n){ cout<<"NIE"<<endl; return 0; } przejdz_graf(j); odwiedzony[j]--; for(int i = j; i < n; i++){ if(!nongrata[i] && !odwiedzony[i]){ cout<<0<<endl; return 0; } } set<int> max_set; for(int i = j; i < n; i++){ if(odwiedzony[i] >= ile_cykli) max_set.insert(i); } cout<<max_set.size()<<endl; set<int>::iterator it; for(it = max_set.begin(); it != max_set.end(); it++){ cout<<(*it) + 1<<" "; } cout<<endl; 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 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 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | #include <iostream> #include <vector> #include <set> using namespace std; int odwiedzony[500000] = {0}; int ile_cykli = 0; bool nongrata[500000]; vector<int> out[500000]; vector<int> in[500000]; int ilein[500000]; int ileout[500000]; void usunin(int s){ nongrata[s] = true; vector<int>::iterator it; for(it = out[s].begin(); it != out[s].end(); it++){ if(!nongrata[*it]){ ilein[*it]--; if(ilein[*it] == 0) usunin(*it); } } } void usunout(int s){ nongrata[s] = true; vector<int>::iterator it; for(it = in[s].begin(); it != in[s].end(); it++){ if(!nongrata[*it]){ ileout[*it]--; if(ileout[*it] == 0) usunout(*it); } } } void przejdz_graf(int s){ if(odwiedzony[s] > 0){ odwiedzony[s]++; ile_cykli++; } if(odwiedzony[s] == 0){ vector<int>::iterator it; for(it = out[s].begin(); it != out[s].end(); it++){ if(!nongrata[s]){ odwiedzony[s]++; przejdz_graf(*it); } } } } int main(){ int n,m; cin>>n>>m; int a,b; for(int i = 0; i < m; i++){ cin>>a>>b; out[a-1].push_back(b-1); in[b-1].push_back(a-1); } for(int i = 0; i < n; i++){ ilein[i] = in[i].size(); ileout[i] = out[i].size(); } for(int i = 0; i < n; i++){ if(!nongrata[i]){ if(ilein[i] == 0) usunin(i); if(ileout[i] == 0) usunout(i); } } int j = 0; while(j < n && nongrata[j]) j++; if(j == n){ cout<<"NIE"<<endl; return 0; } przejdz_graf(j); odwiedzony[j]--; for(int i = j; i < n; i++){ if(!nongrata[i] && !odwiedzony[i]){ cout<<0<<endl; return 0; } } set<int> max_set; for(int i = j; i < n; i++){ if(odwiedzony[i] >= ile_cykli) max_set.insert(i); } cout<<max_set.size()<<endl; set<int>::iterator it; for(it = max_set.begin(); it != max_set.end(); it++){ cout<<(*it) + 1<<" "; } cout<<endl; return 0; } |