#include <bits/stdc++.h> using namespace std; vector<int> G[500000]; int cykle[500000]; set<int> cyklowe; int ncykli; bool dfs(int x) { // fprintf(stderr, "Wchodze do wierzcholka %d po raz %d\n", x+1, cykle[x]+1); if (cykle[x]++) { ncykli++; cyklowe.insert(x); return true; } bool ret = false; for (vector<int>::iterator it = G[x].begin(); it != G[x].end(); it++) if (dfs(*it)) { if (cyklowe.find(x)!=cyklowe.end()) cyklowe.erase(x); if (cyklowe.size()) { ret = true; cykle[x]++; } } if (cyklowe.find(x)!=cyklowe.end()) cyklowe.erase(x); return ret; } int main() { int n, m, i, v, maxn=0; scanf("%d%d", &n, &m); while (m--) { scanf("%d%d", &i, &v); G[--i].push_back(--v); } v = 0; for (i=0; i<n; i++) if (!cykle[i]) dfs(i); for (i=0; i<n; i++) { maxn = max(maxn, --cykle[i]); // fprintf(stderr, "w wierzcholku %d jest %d cykli\n", i+1, cykle[i]); if (cykle[i] == ncykli) v++; } if (!maxn) puts("NIE"); else { printf("%d\n", v); for (i=0; i<n; i++) if (cykle[i] == ncykli) printf("%d ", i+1); 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 49 50 51 52 53 54 55 56 57 58 59 | #include <bits/stdc++.h> using namespace std; vector<int> G[500000]; int cykle[500000]; set<int> cyklowe; int ncykli; bool dfs(int x) { // fprintf(stderr, "Wchodze do wierzcholka %d po raz %d\n", x+1, cykle[x]+1); if (cykle[x]++) { ncykli++; cyklowe.insert(x); return true; } bool ret = false; for (vector<int>::iterator it = G[x].begin(); it != G[x].end(); it++) if (dfs(*it)) { if (cyklowe.find(x)!=cyklowe.end()) cyklowe.erase(x); if (cyklowe.size()) { ret = true; cykle[x]++; } } if (cyklowe.find(x)!=cyklowe.end()) cyklowe.erase(x); return ret; } int main() { int n, m, i, v, maxn=0; scanf("%d%d", &n, &m); while (m--) { scanf("%d%d", &i, &v); G[--i].push_back(--v); } v = 0; for (i=0; i<n; i++) if (!cykle[i]) dfs(i); for (i=0; i<n; i++) { maxn = max(maxn, --cykle[i]); // fprintf(stderr, "w wierzcholku %d jest %d cykli\n", i+1, cykle[i]); if (cykle[i] == ncykli) v++; } if (!maxn) puts("NIE"); else { printf("%d\n", v); for (i=0; i<n; i++) if (cykle[i] == ncykli) printf("%d ", i+1); puts(""); } return 0; } |