#include <bits/stdc++.h> using namespace std; const int MAXN = 500000; int n, m, a, b; bool blocked[MAXN + 5], vis[MAXN + 5]; vector <int> G[MAXN + 5]; vector <int> res; bool cycle_from(int v); int main() { scanf("%d %d", &n, &m); for(int i = 0; i < m; ++i) { scanf("%d %d", &a, &b); G[a].push_back(b); } bool is_cycle = false; for(int i = 1; i <= n; ++i) { if(cycle_from(i)) { is_cycle = true; break; } } if(!is_cycle) { printf("NIE\n"); return 0; } for(int i = 1; i <= n; ++i) { blocked[i] = true; bool no_cycle = true; for(int j = 1; j <= n; ++j) { if(j == i) continue; if(cycle_from(j)) { no_cycle = false; break; } } if(no_cycle) res.push_back(i); blocked[i] = false; } printf("%d\n", res.size()); sort(res.begin(), res.end()); for(int i = 0; i < res.size(); ++i) { printf("%d ", res[i]); } return 0; } bool cycle_from(int v) { for(int i = 1; i <= n; ++i) vis[i] = false; queue <int> Q; Q.push(v); while(!Q.empty()) { int u = Q.front(); Q.pop(); if(vis[u] && u == v) return true; for(int i = 0; i < G[u].size(); ++i) { if(!vis[G[u][i]] && !blocked[G[u][i]]) { vis[G[u][i]] = true; Q.push(G[u][i]); } } } return false; }
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 | #include <bits/stdc++.h> using namespace std; const int MAXN = 500000; int n, m, a, b; bool blocked[MAXN + 5], vis[MAXN + 5]; vector <int> G[MAXN + 5]; vector <int> res; bool cycle_from(int v); int main() { scanf("%d %d", &n, &m); for(int i = 0; i < m; ++i) { scanf("%d %d", &a, &b); G[a].push_back(b); } bool is_cycle = false; for(int i = 1; i <= n; ++i) { if(cycle_from(i)) { is_cycle = true; break; } } if(!is_cycle) { printf("NIE\n"); return 0; } for(int i = 1; i <= n; ++i) { blocked[i] = true; bool no_cycle = true; for(int j = 1; j <= n; ++j) { if(j == i) continue; if(cycle_from(j)) { no_cycle = false; break; } } if(no_cycle) res.push_back(i); blocked[i] = false; } printf("%d\n", res.size()); sort(res.begin(), res.end()); for(int i = 0; i < res.size(); ++i) { printf("%d ", res[i]); } return 0; } bool cycle_from(int v) { for(int i = 1; i <= n; ++i) vis[i] = false; queue <int> Q; Q.push(v); while(!Q.empty()) { int u = Q.front(); Q.pop(); if(vis[u] && u == v) return true; for(int i = 0; i < G[u].size(); ++i) { if(!vis[G[u][i]] && !blocked[G[u][i]]) { vis[G[u][i]] = true; Q.push(G[u][i]); } } } return false; } |