//na podstawie ksiazki "algorytmika praktyczna" #include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> using namespace std; typedef vector<int> VI; typedef long long LL; int ss[500000]; int cykle[500000]; int cyk; int n, m, b, e, k; bool f, f2; #define FOR(x, b, e) for(int x = b; x <= (e); ++x) #define FORD(x, b, e) for(int x = b; x >= (e); --x) #define REP(x, n) for(int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back #define ST first #define ND second #include <list> template<class V, class E> struct Graph { struct Ed : E { int v; Ed(E p, int w) : E(p), v(w) {} }; struct Ve : V, vector<Ed> {}; vector<Ve> g; Graph(int n = 0) : g(n) {} void EdgeD(int b, int e, E d = E()) { g[b].PB(Ed(d, e)); } void Write() { REP(x, SIZE(g)) { cout << x << ":"; FOREACH(it, g[x]) cout << " " << it->v; cout << endl; } } VI vis; VI curr; void SccDfs(int v, int nr, bool phase){ curr.PB(v); g[v].t = 1; if(!phase) vis[v] = nr; FOREACH(it, g[v]) if (g[it->v].t == -1) SccDfs(it->v, nr, phase); else if(!phase) { bool flag = false; cyk++; FOREACH(it2, curr) { if((*it2) == it->v) flag = true; if(flag) { cykle[*it2]++; } } } if(phase) vis.PB(v); else g[v].t = nr; curr.pop_back(); } void Scc() { Graph<V,E> gt(SIZE(g)), *tab[]={this, >}; gt.vis.resize(SIZE(g), -1); vis.clear(); REP(i,SIZE(g)) FOREACH(it,g[i]) gt.EdgeD(it->v, i); REP(i, 2){ FOREACH(it, tab[i]->g) it->t = -1; int comp = 0, v; FORD(j, SIZE(g) - 1, 0) if (tab[i]->g[v = (i ? vis[j] : j)].t == -1) tab[i]->SccDfs(v, comp++, 1 - i); } REP(i, SIZE(g)) g[i].t = gt.g[i].t; return; } }; struct Ve {}; struct Vs { int t; }; int main() { scanf("%d%d",&n,&m); Graph<Vs, Ve> g(n); REP(x, m) { scanf("%d%d",&b,&e); b--; e--; g.EdgeD(b, e); } g.Scc(); REP(x, n) { ss[g.g[x].t]++; } REP(x, n) { if(f && ss[x] > 1) f2 = true; if(ss[x] > 1) f = true; } if(!f) printf("NIE\n"); else { if(f2) { printf("0\n\n"); } else { REP(x, n) if(cykle[x] == cyk) k++; printf("%d\n", k); REP(x, n) if(cykle[x] == cyk) printf("%d ", x + 1); 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 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 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | //na podstawie ksiazki "algorytmika praktyczna" #include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> using namespace std; typedef vector<int> VI; typedef long long LL; int ss[500000]; int cykle[500000]; int cyk; int n, m, b, e, k; bool f, f2; #define FOR(x, b, e) for(int x = b; x <= (e); ++x) #define FORD(x, b, e) for(int x = b; x >= (e); --x) #define REP(x, n) for(int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back #define ST first #define ND second #include <list> template<class V, class E> struct Graph { struct Ed : E { int v; Ed(E p, int w) : E(p), v(w) {} }; struct Ve : V, vector<Ed> {}; vector<Ve> g; Graph(int n = 0) : g(n) {} void EdgeD(int b, int e, E d = E()) { g[b].PB(Ed(d, e)); } void Write() { REP(x, SIZE(g)) { cout << x << ":"; FOREACH(it, g[x]) cout << " " << it->v; cout << endl; } } VI vis; VI curr; void SccDfs(int v, int nr, bool phase){ curr.PB(v); g[v].t = 1; if(!phase) vis[v] = nr; FOREACH(it, g[v]) if (g[it->v].t == -1) SccDfs(it->v, nr, phase); else if(!phase) { bool flag = false; cyk++; FOREACH(it2, curr) { if((*it2) == it->v) flag = true; if(flag) { cykle[*it2]++; } } } if(phase) vis.PB(v); else g[v].t = nr; curr.pop_back(); } void Scc() { Graph<V,E> gt(SIZE(g)), *tab[]={this, >}; gt.vis.resize(SIZE(g), -1); vis.clear(); REP(i,SIZE(g)) FOREACH(it,g[i]) gt.EdgeD(it->v, i); REP(i, 2){ FOREACH(it, tab[i]->g) it->t = -1; int comp = 0, v; FORD(j, SIZE(g) - 1, 0) if (tab[i]->g[v = (i ? vis[j] : j)].t == -1) tab[i]->SccDfs(v, comp++, 1 - i); } REP(i, SIZE(g)) g[i].t = gt.g[i].t; return; } }; struct Ve {}; struct Vs { int t; }; int main() { scanf("%d%d",&n,&m); Graph<Vs, Ve> g(n); REP(x, m) { scanf("%d%d",&b,&e); b--; e--; g.EdgeD(b, e); } g.Scc(); REP(x, n) { ss[g.g[x].t]++; } REP(x, n) { if(f && ss[x] > 1) f2 = true; if(ss[x] > 1) f = true; } if(!f) printf("NIE\n"); else { if(f2) { printf("0\n\n"); } else { REP(x, n) if(cykle[x] == cyk) k++; printf("%d\n", k); REP(x, n) if(cykle[x] == cyk) printf("%d ", x + 1); printf("\n"); } } return 0; } |