Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8.     ios_base::sync_with_stdio(false);
  9.     cin.tie(nullptr);
  10.     cout.tie(nullptr);
  11.     while (cin) {
  12.         int n, m;
  13.         cin >> n >> m;
  14.         vector<vector<int>> list_reversed(n, vector<int>());
  15.         vector<int> reb_out_cnt(n, 0);
  16.         vector<int> cur_cnt(n, 0);
  17.         vector<int> ans(n, -1);
  18.         for (int i = 0; i < m; i++) {
  19.             int a, b;
  20.             cin >> a >> b;
  21.             --a;
  22.             --b;
  23.             reb_out_cnt[a]++;
  24.             list_reversed[b].push_back(a);
  25.         }
  26.         stack<int> stack;
  27.         for (int i = 0; i < n; i++) {
  28.             if (reb_out_cnt[i] == 0) {
  29.                 ans[i] = 0;
  30.                 stack.push(i);
  31.             }
  32.         }
  33.         while (!stack.empty()) {
  34.             int v = stack.top();
  35.             stack.pop();
  36.             if (ans[v] == 0) {
  37.                 for (int i : list_reversed[v]) {
  38.                     ans[i] = 1;
  39.                     stack.push(i);
  40.                 }
  41.             } else if (ans[v] == 1) {
  42.                 for (int i : list_reversed[v]) {
  43.                     cur_cnt[i]++;
  44.                     if (cur_cnt[i] == reb_out_cnt[i]) {
  45.                         ans[i] = 0;
  46.                         stack.push(i);
  47.                     }
  48.                 }
  49.             }
  50.         }
  51.         for (int i : ans) {
  52.             if (i == -1) {
  53.                 cout << "DRAW\n";
  54.             } else if (i == 0) {
  55.                 cout << "SECOND\n";
  56.             } else {
  57.                 cout << "FIRST\n";
  58.             }
  59.         }
  60.         cout << "\n";
  61.     }
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement