#include <iostream> #include <vector> #include <algorithm> #include <unordered_set> class graph { public: graph(int _count) : g(_count) { } void add_edge(int _v1, int _v2) { g[_v1].n.push_back(_v2); } void topo_dfs(int _v) { if (!g[_v].t) { g[_v].t = 1; for (auto &&e : g[_v].n) { if (e != excluded) { topo_dfs(e); } } g[_v].t = --topo; } } void topo_sort() { for (auto &&v : g) { v.t = 0; } topo = g.size(); for (int i = topo - 1; i >= 0; --i) { if (i != excluded) { topo_dfs(i); } } } bool acyclic_exclude(int _excluded) { excluded = _excluded; topo_sort(); for (int i = 0; i < g.size(); ++i) { if (i == excluded) continue; for (auto &&e : g[i].n) { if (e == excluded) continue; if (g[i].t >= g[e].t) { return false; } } } return true; } void cycle_dfs(int _v) { if (g[_v].t2 == 0) { g[_v].t2 = 1; for (auto &&v : g[_v].n) { if (cf >= 0 || cf == -2) break; if (g[v].t2 == 1) { cf = v; break; } cycle_dfs(v); } g[_v].t2 = 2; if (cf >= 0) { c.push_back(_v); if (cf == _v) { cf = -2; } } } } void cycle() { t = 0; cf = -1; for (int i = 0; i < g.size(); ++i) { if (cf != -2) { cycle_dfs(i); } else { break; } } std::reverse(c.begin(), c.end()); } // ----- struct V { int t = -1; int t2 = 0; std::vector<int> n; }; std::vector<V> g; std::vector<int> c; int t; int cf; int topo; int excluded; }; int main() { int n, m; std::cin >> n >> m; graph g(n); for (int i = 0; i < m; ++i) { int a, b; std::cin >> a >> b; g.add_edge(a - 1, b - 1); } if (g.acyclic_exclude(-1)) { std::cout << "NIE" << std::endl; } else { g.cycle(); std::vector<int> result; for (auto &&c : g.c) { if (g.acyclic_exclude(c)) { result.push_back(c + 1); } } std::cout << result.size() << std::endl; std::sort(result.begin(), result.end()); for (auto &&v : result) { std::cout << v << " "; } } 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 136 137 138 139 140 141 142 143 144 145 146 147 148 149 | #include <iostream> #include <vector> #include <algorithm> #include <unordered_set> class graph { public: graph(int _count) : g(_count) { } void add_edge(int _v1, int _v2) { g[_v1].n.push_back(_v2); } void topo_dfs(int _v) { if (!g[_v].t) { g[_v].t = 1; for (auto &&e : g[_v].n) { if (e != excluded) { topo_dfs(e); } } g[_v].t = --topo; } } void topo_sort() { for (auto &&v : g) { v.t = 0; } topo = g.size(); for (int i = topo - 1; i >= 0; --i) { if (i != excluded) { topo_dfs(i); } } } bool acyclic_exclude(int _excluded) { excluded = _excluded; topo_sort(); for (int i = 0; i < g.size(); ++i) { if (i == excluded) continue; for (auto &&e : g[i].n) { if (e == excluded) continue; if (g[i].t >= g[e].t) { return false; } } } return true; } void cycle_dfs(int _v) { if (g[_v].t2 == 0) { g[_v].t2 = 1; for (auto &&v : g[_v].n) { if (cf >= 0 || cf == -2) break; if (g[v].t2 == 1) { cf = v; break; } cycle_dfs(v); } g[_v].t2 = 2; if (cf >= 0) { c.push_back(_v); if (cf == _v) { cf = -2; } } } } void cycle() { t = 0; cf = -1; for (int i = 0; i < g.size(); ++i) { if (cf != -2) { cycle_dfs(i); } else { break; } } std::reverse(c.begin(), c.end()); } // ----- struct V { int t = -1; int t2 = 0; std::vector<int> n; }; std::vector<V> g; std::vector<int> c; int t; int cf; int topo; int excluded; }; int main() { int n, m; std::cin >> n >> m; graph g(n); for (int i = 0; i < m; ++i) { int a, b; std::cin >> a >> b; g.add_edge(a - 1, b - 1); } if (g.acyclic_exclude(-1)) { std::cout << "NIE" << std::endl; } else { g.cycle(); std::vector<int> result; for (auto &&c : g.c) { if (g.acyclic_exclude(c)) { result.push_back(c + 1); } } std::cout << result.size() << std::endl; std::sort(result.begin(), result.end()); for (auto &&v : result) { std::cout << v << " "; } } return 0; } |