Death First Search, ou couper les bons liens

On commence par stocker le nombre de nœuds dans le niveau dans une variable N, le nombre de liens dans une variable L et le nombre de passerelles dans une variable E.

On va ensuite les liens qui relient les nœuds entre eux.

Pour cela, on crée une structure nlinks qui contiendra les liens partant de chaque nœud. Elle contiendra le nombre de liens nb_links et l'ensemble des nœuds adjacents stockés dans un tableau nodes.

Ces structures seront stockées dans un tableau links de manière à ce que l'élément links[i] corresponde au nœud i. (Chaque nœud est numéroté de 0 à N-1.)

Attention : Chaque lien sera donc représenté 2 fois (de A à B et de B à A). Il faudra donc faire attention au moment de retirer un lien du tableau.

Par exemple, le tableau suivant :

…représentera le graphe suivant :

Les nœuds correspondant aux passerelles seront, quant à eux, stockés dans un tableau gateways.

Dans l'exemple ci-dessus, puisque la seule passerelle est le nœud 3, le tableau gateways contiendra seulement la valeur 3.

On suppose que l'agent Bobnet est sur le nœud SI.

À chaque tour de jeu, afin de trouver le lien à couper, on procède de la manière suivante :

• Si l'agent est à un lien d'une passerelle, on coupe le lien reliant SI à la passerelle.
• Sinon, on coupe un lien quelconque autour de l'agent.

Il faudra donc parcourir les différents nœuds adjacents à SI et vérifier s'ils apparaissent dans le tableau gateways. Si on ne trouve aucune passerelle, on coupera de manière arbitraire le premier lien apparaissant dans le tableau links.

Une fois cela fait, pour éviter de recouper un lien déjà coupé, on enlèvera le lien du tableau links en faisant attention à bien enlever les deux apparitions du lien.

On commence par définir la structure nlinks qui contiendra le nombre de liens nb_links et l'ensemble des nœuds adjacents stockés dans un tableau nodes. Elle sera donc implémentée comme un tableau partiellement rempli de taille 50, ce qui permettra de passer la plupart des tests.

Remarque : Comme on ne connaît pas à l'avance le nombre de nœuds adjacents à chaque nœud, il n'est pas possible d'allouer dynamiquement la taille du tableau.

typedef struct node_links {
    int nb_links;
    int nodes[50];
} nlinks;

On définit ensuite la fonction rm_link qui prend en argument un tableau de nlinks appelé links et deux entiers N1 et N2 qui représentent deux nœuds de links, qui ne renvoie rien et qui supprime le lien reliant N1 et N2 en faisant attention à bien supprimer les deux apparitions :

void rm_link (nlinks * links, int N1, int N2) {
  int i;

  int removed1 = 0;
  int removed2 = 0;

  /* N1 -> N2 */
  i = 0;
  while (!removed1 && i < links[N1].nb_links)  {
    if (links[N1].nodes[i] == N2) {
      links[N1].nodes[i] = links[N1].nodes[links[N1].nb_links - 1];
      --links[N1].nb_links;
      removed1 = 1;
    }
    ++i;
  }

  /* N2 -> N1 */
  i = 0;
  while (!removed2 && i < links[N2].nb_links)  {
    if (links[N2].nodes[i] == N1) {
      links[N2].nodes[i] = links[N2].nodes[links[N2].nb_links - 1];
      --links[N2].nb_links;
    }
    ++i;
  }
}

Dans le programme principal, on commence par demander à CodinGame le nombre de nœuds N, le nombre de liens L et le nombre de passerelles E :

int N;
int L;
int E;
scanf("%d%d%d", &N, &L, &E);

On initialise ensuite le tableau links qui contiendra les liens entre les nœuds. CodinGame indiquera les nœuds entre lesquels il doit y avoir un lien, puis le programme les ajoutera dans le tableau links :

int i;
nlinks links[500];

for (i = 0; i < L; i++) {
  int N1;
  int N2;
  scanf("%d%d", &N1, &N2);

  links[N1].nodes[links[N1].nb_links] = N2;
  ++links[N1].nb_links;

  links[N2].nodes[links[N2].nb_links] = N1;
  ++links[N2].nb_links;
 }

On fait de même avec la tableau gateways qui contiendra les passerelles du réseau :

int gateways[20];

for (i = 0; i < E; i++) {
  int EI;
  scanf("%d", &EI);
  gateways[i] = EI;
 }

Attention : A cet instant, le programme entre dans une boucle infinie. Chaque itération dans la boucle infinie représentera un tour de jeu. CodinGame arrêtera la boucle infinie lorsque les conditions de victoire, c'est-à-dire, lorsque l'agent Bobnet ne peut plus atteindre aucune passerelle, auront été remplies.

A chaque tour de jeu, CodinGame indiquera la position de l'agent Bobnet qui sera stockée dans une variable SI.

On souhaite voir si l'un des nœuds adjacents à SI est une passerelle. Pour cela, on parcourt l'ensemble des nœuds n du tableau links[SI].nodes et l'ensemble des passerelles g du tableau gateways et on vérifie si on trouve deux valeurs identiques. Si c'est le cas, on supprime le lien entre SI et le nœud gateways[g].

Si on ne trouve rien à la fin du parcours, on supprimera le lien entre SI et le nœud links[SI].nodes[0].

On aura stocké au préalable le deuxième nœud avant la suppression du lien dans une variable C2.

On renvoie ensuite à CodinGame les nœuds SI et C2.

while (1) {
  int SI;
  scanf("%d", &SI);

  int n;
  int g;

  int found = 0;
  int C2;

  n = 0;
  while (!found && (n < links[SI].nb_links)) {
    g = 0;
    while (!found && g < E) {
      if (links[SI].nodes[n] == gateways[g]) {
        found = 1;
        C2 = gateways[g];
        rm_link(links, SI, gateways[g]);
      }
      ++g;
    }
    ++n;
  }

  if (!found) {
    C2 = links[SI].nodes[0];
    rm_link(links, SI, links[SI].nodes[0]);
  }

  printf("%d %d\n", SI, C2);
 }