Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- #include <iostream>
- using namespace std;
- const int maxn = (int)3e5 + 123;
- int pq[maxn];
- int deg[maxn];
- int win[maxn];
- vector <int> a[maxn];
- int st, en;
- int main()
- {
- int n, m;
- while ( scanf("%d%d", &n, &m) == 2) {
- for (int i = 0; i < n; i++) {
- a[i].clear();
- deg[i] = 0;
- win[i] = -1;
- }
- for (int i = 0; i < m; i++) {
- int u, v;
- scanf("%d%d", &v, &u);
- u--, v--;
- a[u].push_back(v);
- deg[v]++;
- }
- st = en = 0;
- for (int i = 0; i < n; i++) if (deg[i] == 0) pq[en++] = i, win[i] = 0;
- while (st != en) {
- int s = pq[st++];
- if (!win[s]) {
- for (auto x : a[s]) {
- if (win[x] != -1) continue;
- win[x] = 1;
- pq[en++] = x;
- }
- } else {
- for (auto x : a[s]) {
- deg[x]--;
- if (deg[x] == 0) {
- win[x] = 0;
- pq[en++] = x;
- }
- }
- }
- }
- for (int i = 0; i < n; i++) {
- if (win[i] == -1) printf("DRAW\n");
- if (win[i] == 1) printf("FIRST\n");
- if (win[i] == 0) printf("SECOND\n");
- }
- printf("\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment