#include<bits/stdc++.h>
#include "coprobber.h"
using namespace std;
const int TAILLE_MAX=500+5;
int nbSom,nbAre,poliCour;
bool existeChem[TAILLE_MAX][TAILLE_MAX];
vector<int> adja[TAILLE_MAX];
int memo[TAILLE_MAX][TAILLE_MAX][2];
int suiv[TAILLE_MAX][TAILLE_MAX];
int degSort[TAILLE_MAX];
int rest[TAILLE_MAX][TAILLE_MAX];
void maj(int posPoli,int posVol,int tour) {
if (memo[posPoli][posVol][tour]==1) {
memo[posPoli][posVol][tour]=0;
if (tour==1) {
for (int i:adja[posPoli]) {
if (memo[i][posVol][0]==1) {
suiv[i][posVol]=posPoli;
maj(i,posVol,0);
}
}
if (memo[posPoli][posVol][0]==1) {
suiv[posPoli][posVol]=1;
maj(posPoli,posVol,0);
}
}
else {
for (int i:adja[posVol]) {
rest[posPoli][i]--;
if (rest[posPoli][i]==0) {
maj(posPoli,i,1);
}
}
}
}
}
int start(int N, bool A[MAX_N][MAX_N]) {
nbSom=N;
for (int i=0;i<nbSom;i++) {
for (int j=0;j<nbSom;j++) {
existeChem[i][j]=A[i][j];
if (existeChem[i][j]) {
adja[i].push_back(j);
degSort[i]++;
}
memo[i][j][0]=1;
memo[i][j][1]=1;
}
}
for (int i=0;i<nbSom;i++) {
for (int j=0;j<nbSom;j++) {
rest[i][j]=degSort[j];
}
}
for (int i=0;i<nbSom;i++) {
maj(i,i,0);
maj(i,i,1);
}
int pb;
for (int i=0;i<nbSom;i++) {
pb=0;
for (int j=0;j<nbSom;j++) {
if (memo[i][j][0]==1) {
pb=1;
}
}
if (pb==0) {
poliCour=i;
return i;
}
}
return -1;
}
int nextMove(int posVol) {
return suiv[poliCour][posVol];
}
