niyaznigmatullin

Untitled

Sep 8th, 2015
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. int const N = 1234567;
  4.  
  5. int p[N], ans[N], q[N], deg[N];
  6. std::vector<int> edges[N];
  7.  
  8.  
  9. int main() {
  10.     int n, m;
  11.     scanf("%d%d", &n, &m);
  12.     for (int i = 0; i < m; i++) {
  13.         int v, u;
  14.         scanf("%d%d", &v, &u);
  15.         --v;
  16.         --u;
  17.         edges[v].push_back(u);
  18.         deg[u]++;
  19.     }
  20.     int head = 0;
  21.     int tail = 0;
  22.     for (int i = 0; i < n; i++) if (deg[i] == 0) q[tail++] = i;
  23.     while (head < tail) {
  24.         int v = q[head++];
  25.         for (int to : edges[v]) {
  26.             --deg[to];
  27.             if (deg[to] == 0) {
  28.                 q[tail++] = to;
  29.             }
  30.         }
  31.     }
  32.     if (head == n) {
  33.         puts("NO");
  34.         return 0;
  35.     }
  36.     int v = -1;
  37.     for (int i = 0; i < n; i++) {
  38.         if (deg[i] == 0) continue;
  39.         v = i;
  40.         for (int j : edges[i])
  41.             p[j] = i;
  42.     }
  43.     for (int i = 0; i < n; i++) v = p[v];
  44.     int u = p[v];
  45.     int ac = 0;
  46.     while (true) {
  47.         ans[ac++] = u;
  48.         if (u == v) break;
  49.         u = p[u];
  50.     }
  51.     std::reverse(ans, ans + ac);
  52.     puts("YES");
  53.     for (int i = 0; i < ac; i++) {
  54.         if (i > 0) putchar(' ');
  55.         printf("%d", ans[i] + 1);
  56.     }
  57.     puts("");
  58. }
Advertisement
Add Comment
Please, Sign In to add comment