#include <iomanip> #include <iostream> #include <queue> #include <utility> #include <algorithm> #include <cassert> #include <string> #include <vector> #include <set> #include <map> #include <cstdlib> #include <unordered_map> using namespace std; #define ALL(x) x.begin(), x.end() #define VAR(a,b) __typeof (b) a = b #define REP(i,n) for (int _n=(n), i=0; i<_n; ++i) #define FOR(i,a,b) for (int _b=(b), i=(a); i<=_b; ++i) #define FORD(i,a,b) for (int _b=(b), i=(a); i>=_b; --i) #define FORE(i,a) for (VAR(i,a.begin ()); i!=a.end (); ++i) #define IN(x) int x; cin >> x #define PB push_back #define MP make_pair #define ST first #define ND second typedef vector<int> VI; typedef long long LL; typedef pair<int,int> PII; typedef double LD; const int MAXN = 5 * int(1e5); int n; VI on_stack; VI stack; VI v[MAXN]; VI is_disabled, vis; VI any_cycle; bool found_cycle; void dfs(int node) { on_stack[node] = 1; vis[node] = 1; stack.PB(node); FORE(it,v[node]) if (found_cycle) break; else if (is_disabled[*it]) continue; else if (!vis[*it]) dfs(*it); else { if (!on_stack[*it]) continue; found_cycle = true; if (any_cycle.empty()) { bool found_first = false; FORE(jt, stack) { if (!found_first && *jt != *it) continue; found_first = true; any_cycle.PB(*jt); } } } on_stack[node] = 0; stack.pop_back(); } int main() { ios_base::sync_with_stdio(0); cout.setf(ios::fixed); int m; cin >> n >> m; REP(i,m) { IN(a); IN(b); --a; --b; v[a].PB(b); } REP(i,n) random_shuffle(ALL(v[i])); on_stack = is_disabled = vis = VI(n, 0); found_cycle = false; VI to_try; REP(i,n) to_try.PB(i); random_shuffle(ALL(to_try)); FORE(it, to_try) if (any_cycle.empty() && !vis[*it]) dfs(*it); if (!found_cycle) { cout << "NIE\n"; return 0; } VI res; FORE(it, any_cycle) { found_cycle = false; is_disabled[*it] = 1; vis = VI(n, 0); REP(i, n) if (!found_cycle && !vis[i]) dfs(i); is_disabled[*it] = 0; if (!found_cycle) res.PB(*it); } sort(ALL(res)); cout << res.size() << endl; if (res.empty()) return 0; FORE(it, res) 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 115 | #include <iomanip> #include <iostream> #include <queue> #include <utility> #include <algorithm> #include <cassert> #include <string> #include <vector> #include <set> #include <map> #include <cstdlib> #include <unordered_map> using namespace std; #define ALL(x) x.begin(), x.end() #define VAR(a,b) __typeof (b) a = b #define REP(i,n) for (int _n=(n), i=0; i<_n; ++i) #define FOR(i,a,b) for (int _b=(b), i=(a); i<=_b; ++i) #define FORD(i,a,b) for (int _b=(b), i=(a); i>=_b; --i) #define FORE(i,a) for (VAR(i,a.begin ()); i!=a.end (); ++i) #define IN(x) int x; cin >> x #define PB push_back #define MP make_pair #define ST first #define ND second typedef vector<int> VI; typedef long long LL; typedef pair<int,int> PII; typedef double LD; const int MAXN = 5 * int(1e5); int n; VI on_stack; VI stack; VI v[MAXN]; VI is_disabled, vis; VI any_cycle; bool found_cycle; void dfs(int node) { on_stack[node] = 1; vis[node] = 1; stack.PB(node); FORE(it,v[node]) if (found_cycle) break; else if (is_disabled[*it]) continue; else if (!vis[*it]) dfs(*it); else { if (!on_stack[*it]) continue; found_cycle = true; if (any_cycle.empty()) { bool found_first = false; FORE(jt, stack) { if (!found_first && *jt != *it) continue; found_first = true; any_cycle.PB(*jt); } } } on_stack[node] = 0; stack.pop_back(); } int main() { ios_base::sync_with_stdio(0); cout.setf(ios::fixed); int m; cin >> n >> m; REP(i,m) { IN(a); IN(b); --a; --b; v[a].PB(b); } REP(i,n) random_shuffle(ALL(v[i])); on_stack = is_disabled = vis = VI(n, 0); found_cycle = false; VI to_try; REP(i,n) to_try.PB(i); random_shuffle(ALL(to_try)); FORE(it, to_try) if (any_cycle.empty() && !vis[*it]) dfs(*it); if (!found_cycle) { cout << "NIE\n"; return 0; } VI res; FORE(it, any_cycle) { found_cycle = false; is_disabled[*it] = 1; vis = VI(n, 0); REP(i, n) if (!found_cycle && !vis[i]) dfs(i); is_disabled[*it] = 0; if (!found_cycle) res.PB(*it); } sort(ALL(res)); cout << res.size() << endl; if (res.empty()) return 0; FORE(it, res) cout << *it + 1 << " "; cout << endl; return 0; } |