#include <bits/stdc++.h>
#include "train.h"
using namespace std;
#define pb push_back
typedef vector<int> vi;
const int len = 5005;
int vis[len], block[len], bel[len], deg[len], n;
vector<int> adj[len];
void print(vi vec){
for (int i = 0; i < vec.size(); i++)
printf(" %d", vec[i]);
printf("\n");
}
vi operator-(vi a, vi b){
sort(a.begin(), a.end());
sort(b.begin(), b.end());
vi res;
for (int i = 0, j = 0; i < a.size(); i++){
while (j < b.size() && b[j] < a[i])
j++;
if (j == b.size() || b[j] > a[i])
res.pb(a[i]);
}
return res;
}
vi func(int sub, vi base){
//printf("ins func: sub = %d, base =", sub), print(base);
for (int u = 0; u < n; u++)
vis[u] = deg[u] = 0;
for (int u = 0; u < n; u++){
if (block[u]) continue;
for (auto v: adj[u])
if (!block[v])
deg[v]++;
}
//for (int u = 0; u < n; u++)
// printf("u = %d, deg = %d\n", u, deg[u]);
queue<int> myq;
for (auto u: base)
vis[u] = 1, myq.push(u);
while (!myq.empty()){
int u = myq.front();
myq.pop();
for (auto v: adj[u]){
if (block[v] || vis[v])
continue;
if (bel[v] == sub)
vis[v] = 1, myq.push(v);
else{
deg[v]--;
if (!deg[v])
vis[v] = 1, myq.push(v);
}
}
}
vi res;
for (int i = 0; i < n; i++)
if (!block[i] && vis[i])
res.pb(i);
//printf("and res ="), print(res);
return res;
}
vi who_wins(vi B, vi spec, vi U, vi V) {
n = B.size();
for (int i = 0; i < U.size(); i++){
int a = U[i], b = V[i];
adj[b].pb(a);
}
vi graph;
for (int i = 0; i < n; i++)
graph.pb(i), block[i] = 0, bel[i] = B[i];
while (true){
vi reach, rest;
for (auto u: graph)
if (spec[u])
reach.pb(u);
reach = func(1, reach);
rest = func(0, graph-reach);
/*printf("graph:"), print(graph);
printf("reach:"), print(reach);
printf("rest:"), print(rest);*/
if (rest.size() == 0)
break;
graph = graph-rest;
}
vi res(n, 0);
for (auto u: graph)
res[u] = 1;
return res;
}
/*
3 6
1 0 0
0 1 0
0 0
0 1
1 0
1 2
2 2
2 1
*/
