#include <cstdio> #include <vector> using namespace std; const int MAXN = 1000000; int n,m; vector<int> G[MAXN]; int jest[MAXN] ,vis[MAXN]; bool dfs(int x, int e = -1) { vis[x] = 1; jest[x] = 1; for (auto y: G[x]) { if (y == e) continue; if (jest[y]) {jest[x] = 0; return true;} if (!vis[y] && dfs(y, e)) {jest[x] = 0; return true;} } jest[x] = 0; return false; } int main() { scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); a--; b--; G[a].push_back(b); } bool cykl = 0; for (int i = 0; i < n; i++) if (!vis[i]) { cykl |= dfs(i); } if (!cykl) { puts("NIE"); return 0; } vector<int> res; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) vis[j] = 0; cykl = 0; for (int j = 0; j < n; j++) if (j != i && !vis[j]) { cykl |= dfs(j,i); } if (!cykl) res.push_back(i+1); } printf("%d\n", res.size()); for (auto x: res) printf("%d ", x); puts(""); 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 | #include <cstdio> #include <vector> using namespace std; const int MAXN = 1000000; int n,m; vector<int> G[MAXN]; int jest[MAXN] ,vis[MAXN]; bool dfs(int x, int e = -1) { vis[x] = 1; jest[x] = 1; for (auto y: G[x]) { if (y == e) continue; if (jest[y]) {jest[x] = 0; return true;} if (!vis[y] && dfs(y, e)) {jest[x] = 0; return true;} } jest[x] = 0; return false; } int main() { scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); a--; b--; G[a].push_back(b); } bool cykl = 0; for (int i = 0; i < n; i++) if (!vis[i]) { cykl |= dfs(i); } if (!cykl) { puts("NIE"); return 0; } vector<int> res; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) vis[j] = 0; cykl = 0; for (int j = 0; j < n; j++) if (j != i && !vis[j]) { cykl |= dfs(j,i); } if (!cykl) res.push_back(i+1); } printf("%d\n", res.size()); for (auto x: res) printf("%d ", x); puts(""); return 0; } |