nikolaj

Untitled

May 10th, 2015
244
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.14 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = (int)3e5 + 123;
  9. int pq[maxn];
  10. int deg[maxn];
  11. int win[maxn];
  12. vector <int> a[maxn];
  13. int st, en;
  14.  
  15. int main()
  16. {
  17.     int n, m;
  18.     while ( scanf("%d%d", &n, &m) == 2) {
  19.             for (int i = 0; i < n; i++) {
  20.                 a[i].clear();
  21.                 deg[i] = 0;
  22.                 win[i] = -1;
  23.             }
  24.             for (int i = 0; i < m; i++) {
  25.                 int u, v;
  26.                 scanf("%d%d", &v, &u);
  27.                 u--, v--;
  28.                 a[u].push_back(v);
  29.                 deg[v]++;
  30.             }
  31.             st = en = 0;
  32.             for (int i = 0; i < n; i++) if (deg[i] == 0) pq[en++] = i, win[i] = 0;
  33.             while (st != en) {
  34.                 int s = pq[st++];
  35.                 if (!win[s]) {
  36.                     for (auto x : a[s]) {
  37.                         if (win[x] != -1) continue;
  38.                         win[x] = 1;
  39.                         pq[en++] = x;
  40.                     }
  41.                 } else {
  42.                     for (auto x : a[s]) {
  43.                         deg[x]--;
  44.                         if (deg[x] == 0) {
  45.                             win[x] = 0;
  46.                             pq[en++] = x;
  47.                         }
  48.                     }
  49.                 }
  50.             }
  51.             for (int i = 0; i < n; i++) {
  52.                 if (win[i] == -1) printf("DRAW\n");
  53.                 if (win[i] == 1) printf("FIRST\n");
  54.                 if (win[i] == 0) printf("SECOND\n");
  55.             }
  56.             printf("\n");
  57.     }
  58.     return 0;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment