#include <cstdio> #include <algorithm> #include <vector> #include <set> using namespace std; struct wp { vector <int> v; int odw;//0-nodw, 1-prz, 2-odw }t[500005]; vector <int> sci; set <int> kan, pom; bool cykl; void view () { for (set<int>::iterator it=kan.begin(); it!=kan.end(); it++) printf ("%d ", *it); printf ("\n"); } void viewv () { for (vector<int>::iterator it=sci.begin(); it!=sci.end(); it++) printf ("%d ", *it); } void czwsp (int a) { for (vector<int>::reverse_iterator it=sci.rbegin(); it!=sci.rend(); it++) { if (kan.find(*it)!=kan.end()) pom.insert(*it); if (*it==a) break; } kan=pom; pom.clear(); } void DFS (int a) { if (t[a].odw==2) return; if (t[a].odw==1) { cykl=true; //viewv(); printf ("przed : "); view(); czwsp(a); //viewv(); printf ("po : "); view(); return; } t[a].odw=1; sci.push_back(a); for (vector <int>::iterator it=t[a].v.begin(); it!=t[a].v.end(); it++) DFS(*it); sci.pop_back(); t[a].odw=2; } int main () { int n, m, x, y; scanf ("%d%d", &n, &m); for (int i=1; i<=n; i++) kan.insert(i); for (int i=0; i<m; i++) { scanf ("%d%d", &x, &y); t[x].v.push_back(y); } DFS(1); if (cykl==false) printf ("NIE"); else { printf ("%d\n", kan.size()); for (set <int>::iterator it=kan.begin(); it!=kan.end(); it++) printf ("%d ", *it); } return 0; } /* 11 12 1 2 2 3 3 7 7 6 6 5 5 4 4 3 3 10 8 3 10 11 11 9 9 8 */
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 | #include <cstdio> #include <algorithm> #include <vector> #include <set> using namespace std; struct wp { vector <int> v; int odw;//0-nodw, 1-prz, 2-odw }t[500005]; vector <int> sci; set <int> kan, pom; bool cykl; void view () { for (set<int>::iterator it=kan.begin(); it!=kan.end(); it++) printf ("%d ", *it); printf ("\n"); } void viewv () { for (vector<int>::iterator it=sci.begin(); it!=sci.end(); it++) printf ("%d ", *it); } void czwsp (int a) { for (vector<int>::reverse_iterator it=sci.rbegin(); it!=sci.rend(); it++) { if (kan.find(*it)!=kan.end()) pom.insert(*it); if (*it==a) break; } kan=pom; pom.clear(); } void DFS (int a) { if (t[a].odw==2) return; if (t[a].odw==1) { cykl=true; //viewv(); printf ("przed : "); view(); czwsp(a); //viewv(); printf ("po : "); view(); return; } t[a].odw=1; sci.push_back(a); for (vector <int>::iterator it=t[a].v.begin(); it!=t[a].v.end(); it++) DFS(*it); sci.pop_back(); t[a].odw=2; } int main () { int n, m, x, y; scanf ("%d%d", &n, &m); for (int i=1; i<=n; i++) kan.insert(i); for (int i=0; i<m; i++) { scanf ("%d%d", &x, &y); t[x].v.push_back(y); } DFS(1); if (cykl==false) printf ("NIE"); else { printf ("%d\n", kan.size()); for (set <int>::iterator it=kan.begin(); it!=kan.end(); it++) printf ("%d ", *it); } return 0; } /* 11 12 1 2 2 3 3 7 7 6 6 5 5 4 4 3 3 10 8 3 10 11 11 9 9 8 */ |