#include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<queue> using namespace std; const int MAX = 500001; int n, m, a[MAX], b[MAX]; vector<int> syny[MAX]; vector<int> wynik; bool odwiedzony[MAX], bylo[MAX], mag; void DFS (int w) { if (odwiedzony[w]) { mag = true; return; } odwiedzony[w] = true; bylo[w] = true; for (int i = 0; i < syny[w].size(); i++) { DFS(syny[w][i]); if (mag == true) return; } odwiedzony[w] = false; return; } void wczytaj_dane() { cin >> n >> m; for (int i = 0; i < m; i++) cin >> a[i] >> b[i]; } bool cykl_bez(int w) { for (int i = 1; i <= n; i++) syny[i].clear(); for (int i = 0; i < m; i++) if (a[i] != w && b[i] != w) syny[a[i]].push_back(b[i]); fill (odwiedzony, odwiedzony + n + 1, 0); fill (bylo, bylo + n + 1, 0); mag = false; for (int i = 1; i <= n; i++) { if (!bylo[i]) DFS(i); } return mag; } int main() { wczytaj_dane(); if (!cykl_bez(n + 1)) { cout << "NIE"; return 0; } for (int i = 1; i <= n; i++) if (!cykl_bez(i)) wynik.push_back(i); cout << wynik.size() << endl; for (int i = 0; i < wynik.size(); i++) cout << wynik[i] << " "; 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 | #include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<queue> using namespace std; const int MAX = 500001; int n, m, a[MAX], b[MAX]; vector<int> syny[MAX]; vector<int> wynik; bool odwiedzony[MAX], bylo[MAX], mag; void DFS (int w) { if (odwiedzony[w]) { mag = true; return; } odwiedzony[w] = true; bylo[w] = true; for (int i = 0; i < syny[w].size(); i++) { DFS(syny[w][i]); if (mag == true) return; } odwiedzony[w] = false; return; } void wczytaj_dane() { cin >> n >> m; for (int i = 0; i < m; i++) cin >> a[i] >> b[i]; } bool cykl_bez(int w) { for (int i = 1; i <= n; i++) syny[i].clear(); for (int i = 0; i < m; i++) if (a[i] != w && b[i] != w) syny[a[i]].push_back(b[i]); fill (odwiedzony, odwiedzony + n + 1, 0); fill (bylo, bylo + n + 1, 0); mag = false; for (int i = 1; i <= n; i++) { if (!bylo[i]) DFS(i); } return mag; } int main() { wczytaj_dane(); if (!cykl_bez(n + 1)) { cout << "NIE"; return 0; } for (int i = 1; i <= n; i++) if (!cykl_bez(i)) wynik.push_back(i); cout << wynik.size() << endl; for (int i = 0; i < wynik.size(); i++) cout << wynik[i] << " "; return 0; } |