#include <algorithm> #include <cstdio> #include <stack> #include <vector> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define VAR(v,w) __typeof(w) v=(w) #define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it) #define PB push_back #define ALL(c) (c).begin(),(c).end() typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<bool> VB; int n, m; VVI g; bool belong[500000], ent[500000], ex[500000], rr[500000]; VI l; int aFwd[500000], bFwd[500000], aBack[500000], bBack[500000]; class SCC { int ind; VI index, low; stack<int> s; VB ins; void dfs(int v) { if (res[v] >= 0) return; index[v] = low[v] = ind++; s.push(v); ins[v] = 1; FORE(it,g[v]) { int w = *it; if (index[w] < 0) { dfs(w); low[v] = min(low[v], low[w]); } else if (ins[w]) low[v] = min(low[v], index[w]); } if (low[v] == index[v]) { int w; do { w = s.top(); s.pop(); ins[w] = 0; res[w] = k; } while (w != v); ++k; } } public: VI res; int k; SCC() : ind(0), index(n, -1), low(n, -1), s(), ins(n), res(n, -1), k(0) { REP(i,n) dfs(i); } }; void go(int v) { ent[v] = 1; FORE(it,g[v]) { int w = *it; if (!belong[w]) continue; if (ent[w] && !ex[w]) { ++aBack[v]; ++bBack[w]; continue; } ++aFwd[v]; ++bFwd[w]; if (!ent[w]) go(w); } ex[v] = 1; l.PB(v); } int main() { scanf("%d%d", &n, &m); g.resize(n); REP(j,m) { int a, b; scanf("%d%d", &a, &b); --a; --b; g[a].PB(b); } SCC scc; VI c(scc.k); FORE(it,scc.res) ++c[*it]; int comp = -1; REP(k,scc.k) if (c[k] > 1) { if (comp >= 0) { printf("0\n\n"); return 0; } comp = k; } if (comp < 0) { printf("NIE\n"); return 0; } REP(i,n) belong[i] = scc.res[i] == comp; REP(i,n) if (belong[i] && !ex[i]) go(i); reverse(ALL(l)); int fwd = 0, back = 0, backTotal = 0; FORE(it,l) backTotal += aBack[*it]; int r = 0; FORE(it,l) { fwd -= bFwd[*it]; back += bBack[*it]; if (!fwd && back == backTotal) { rr[*it] = 1; ++r; } back -= aBack[*it]; fwd += aFwd[*it]; } printf("%d\n", r); bool first = 1; REP(i,n) if (rr[i]) { printf(first ? "%d" : " %d", i + 1); first = 0; } printf("\n"); }
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 | #include <algorithm> #include <cstdio> #include <stack> #include <vector> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define VAR(v,w) __typeof(w) v=(w) #define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it) #define PB push_back #define ALL(c) (c).begin(),(c).end() typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<bool> VB; int n, m; VVI g; bool belong[500000], ent[500000], ex[500000], rr[500000]; VI l; int aFwd[500000], bFwd[500000], aBack[500000], bBack[500000]; class SCC { int ind; VI index, low; stack<int> s; VB ins; void dfs(int v) { if (res[v] >= 0) return; index[v] = low[v] = ind++; s.push(v); ins[v] = 1; FORE(it,g[v]) { int w = *it; if (index[w] < 0) { dfs(w); low[v] = min(low[v], low[w]); } else if (ins[w]) low[v] = min(low[v], index[w]); } if (low[v] == index[v]) { int w; do { w = s.top(); s.pop(); ins[w] = 0; res[w] = k; } while (w != v); ++k; } } public: VI res; int k; SCC() : ind(0), index(n, -1), low(n, -1), s(), ins(n), res(n, -1), k(0) { REP(i,n) dfs(i); } }; void go(int v) { ent[v] = 1; FORE(it,g[v]) { int w = *it; if (!belong[w]) continue; if (ent[w] && !ex[w]) { ++aBack[v]; ++bBack[w]; continue; } ++aFwd[v]; ++bFwd[w]; if (!ent[w]) go(w); } ex[v] = 1; l.PB(v); } int main() { scanf("%d%d", &n, &m); g.resize(n); REP(j,m) { int a, b; scanf("%d%d", &a, &b); --a; --b; g[a].PB(b); } SCC scc; VI c(scc.k); FORE(it,scc.res) ++c[*it]; int comp = -1; REP(k,scc.k) if (c[k] > 1) { if (comp >= 0) { printf("0\n\n"); return 0; } comp = k; } if (comp < 0) { printf("NIE\n"); return 0; } REP(i,n) belong[i] = scc.res[i] == comp; REP(i,n) if (belong[i] && !ex[i]) go(i); reverse(ALL(l)); int fwd = 0, back = 0, backTotal = 0; FORE(it,l) backTotal += aBack[*it]; int r = 0; FORE(it,l) { fwd -= bFwd[*it]; back += bBack[*it]; if (!fwd && back == backTotal) { rr[*it] = 1; ++r; } back -= aBack[*it]; fwd += aFwd[*it]; } printf("%d\n", r); bool first = 1; REP(i,n) if (rr[i]) { printf(first ? "%d" : " %d", i + 1); first = 0; } printf("\n"); } |