Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- int const N = 1234567;
- int p[N], ans[N], q[N], deg[N];
- std::vector<int> edges[N];
- int main() {
- int n, m;
- scanf("%d%d", &n, &m);
- for (int i = 0; i < m; i++) {
- int v, u;
- scanf("%d%d", &v, &u);
- --v;
- --u;
- edges[v].push_back(u);
- deg[u]++;
- }
- int head = 0;
- int tail = 0;
- for (int i = 0; i < n; i++) if (deg[i] == 0) q[tail++] = i;
- while (head < tail) {
- int v = q[head++];
- for (int to : edges[v]) {
- --deg[to];
- if (deg[to] == 0) {
- q[tail++] = to;
- }
- }
- }
- if (head == n) {
- puts("NO");
- return 0;
- }
- int v = -1;
- for (int i = 0; i < n; i++) {
- if (deg[i] == 0) continue;
- v = i;
- for (int j : edges[i])
- p[j] = i;
- }
- for (int i = 0; i < n; i++) v = p[v];
- int u = p[v];
- int ac = 0;
- while (true) {
- ans[ac++] = u;
- if (u == v) break;
- u = p[u];
- }
- std::reverse(ans, ans + ac);
- puts("YES");
- for (int i = 0; i < ac; i++) {
- if (i > 0) putchar(' ');
- printf("%d", ans[i] + 1);
- }
- puts("");
- }
Advertisement
Add Comment
Please, Sign In to add comment