#include "train.h"
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
using vi = vector<int>;
#define sz(x) int(x.size())
const int mx = 5'000;
vi edge[mx];
vi revedge[mx];
int n, m;
vi a, r;
vi getforced(vi active, vi good, int player)
{
// cerr << "\n\n\n\nCALLED\n";
vi deg(n, 0);
for(int i = 0; i < n; i++)
{
if(!active[i]) continue;
for(int j : edge[i])
{
if(active[j])
deg[i]++;
}
}
queue<int> tbv;
for(int i = 0; i < n; i++)
{
// cerr << i << " -> " << active[i] << ' ' << good[i] << '\n';
if(active[i] && good[i])
{
tbv.push(i);
}
}
while(!tbv.empty())
{
int u = tbv.front();
tbv.pop();
// cerr << "u = " << u << '\n';
for(int v : revedge[u])
{
if(!active[v]) continue;
if(good[v]) continue;
// cerr << v << " : " << a[v] << ' ' << player << '\n';
if(a[v] == player)
{
good[v] = 1;
tbv.push(v);
}
else
{
deg[v]--;
if(deg[v] == 0)
{
good[v] = 1;
tbv.push(v);
}
}
}
}
return good;
}
//a = owner, r = charging
vi who_wins(vi a_, vi r_, vi U, vi V)
{
a = a_;
r = r_;
n = sz(a);
m = sz(U);
for(int j = 0; j < m; j++)
{
edge[U[j]].push_back(V[j]);
revedge[V[j]].push_back(U[j]);
}
vi active(n, 1);
while(1)
{
// cerr << "it\n";
int oldcount = 0;
for(int i = 0; i < n; i++) oldcount += active[i];
vi stations(n, 0);
for(int i = 0; i < n; i++) stations[i] = active[i] && r[i];
// cerr << "stations = ";
// cerr << stations[0] << ' ' << stations[1] << '\n';
vi Areach = getforced(active, stations, 1);
// cerr << "Areach = ";
// cerr << Areach[0] << ' ' << Areach[1] << '\n';
vi nonAreach(n);
for(int i = 0; i < n; i++)
{
if(!active[i])
nonAreach[i] = 0;
else
nonAreach[i] = !Areach[i];
}
// cerr << nonAreach[0] << ' ' << nonAreach[1] << '\n';
vi Breach = getforced(active, nonAreach, 0);
for(int i = 0; i < n; i++)
if(Breach[i])
active[i] = 0;
// cerr << Breach[0] << ' ' << Breach[1] << '\n';
int newcount = 0;
for(int i = 0; i < n; i++) newcount += active[i];
// cerr << oldcount << " : " << newcount << '\n';
// for(int i = 0; i < n; i++) cerr << active[i] << ' ';
// cerr << '\n';
if(oldcount == newcount) break;
}
return active;
}
