#include "train.h"
#include <deque>
#include <vector>
using namespace std;
int nbSommets;
vector<int> nouvDegs;
vector<bool> nouvGagnants;
vector<int> estMax;
vector<bool> estPasse;
vector<int> parents[6000];
void explore(int sommet) {
if(estPasse[sommet])
return;
estPasse[sommet] = true;
for(int parent : parents[sommet]) {
if(nouvGagnants[parent]) continue;
if(estMax[parent]) {
nouvGagnants[parent] = true;
explore(parent);
}
else {
nouvDegs[parent]--;
if(nouvDegs[parent] == 0) {
nouvGagnants[parent] = true;
explore(parent);
}
}
}
}
vector<int> who_wins(vector<int> _estMax, vector<int> estRecharge,
vector<int> debs, vector<int> fins) {
estMax = _estMax;
nbSommets = estMax.size();
vector<int> degs(nbSommets, 0);
for(int iArc = 0;iArc < (int)debs.size();iArc++) {
parents[fins[iArc]].push_back(debs[iArc]);
degs[debs[iArc]]++;
}
int nbRecharges = 0;
for(int iSommet = 0;iSommet < nbSommets;iSommet++) {
if(estRecharge[iSommet])
nbRecharges += 1;
}
vector<bool> gagnants(nbSommets, true);
for(int iFois = 0;iFois <= nbRecharges + 3;iFois++) {
nouvDegs = degs;
nouvGagnants = vector<bool>(nbSommets, false);
estPasse = vector<bool>(nbSommets, false);
for(int iSommet = 0;iSommet < nbSommets;iSommet++) {
if(gagnants[iSommet] && estRecharge[iSommet] && !nouvGagnants[iSommet]) {
explore(iSommet);
}
}
gagnants = nouvGagnants;
}
vector<int> estGagnant;
for(int iSommet = 0;iSommet < nbSommets;iSommet++) {
estGagnant.push_back(gagnants[iSommet]);
}
return estGagnant;
}
