Amis d’amis

Sur Facebook, vous avez un certain nombre d'amis. Vous pouvez aller sur la page de vos amis afin de savoir combien ils ont d'amis chacuns. Facebook va également vous indiquer combien d'amis vous avez en commun avec chacun de vos amis. Cependant, vous aimeriez en savoir un peu plus. Plus précisément, vous vous demandez combien il y a de gens qui font partie des amis de vos amis et qui ne font pas déjà partie de vos amis.

Compter à la main prendrait bien trop de temps, donc vous décidez d'écrire un plugin Facebook pour cela. Votre plugin doit prendre en entrée votre identifiant, ainsi qu'une liste de relations d'amitiés, c'est-à-dire une liste de paires d'identifiants de personnes. Il doit ensuite calculer le nombre d'amis de vos amis qui ne sont pas (encore) vos amis.

Limites de temps et de mémoire (Python)

  • Temps : 1 s sur une machine à 1 GHz.
  • Mémoire : 32 000 ko.

Contraintes

  • 0 <= I < 65 000, où I est un identifiant.
  • 0 <= N < 100 000, où N est le nombre de relations d'amitiés.

Entrée

  • La première ligne contient un seul entier I : votre identifiant.
  • La seconde ligne contient un seul entier N : le nombre de relations d'amitiés.
  • Les N lignes suivantes contiennent deux entiers chacune, qui sont deux identifiants de personnes amies l'une de l'autre.

Noter que l'amitié est toujours réciproque : si I1 est ami de I2 alors I2 est ami de I1. On donnera soit (I1,I2) soit (I2,I1) dans l'entrée, mais pas les deux.

De plus, une personne n'est jamais amie d'elle-même, i.e. I1 et I2 sont toujours différents.

Sortie

Vous devez afficher un entier sur une ligne : le nombre d'amis d'amis qui ne sont pas des amis directs.

Exemple

entrée :

0
11
0 1
0 2
0 3
1 2
1 3
2 3
1 4
2 5
2 4
3 6
7 8

sortie :

3

Commentaires

Squelette de code C++ :
#include <cstdio>

const int MAX_RELATIONS = 100000;

int relations[MAX_RELATIONS][2];

int main()
{
   int nbRelations, identifiant, X;

   scanf("%d%d", &identifiant, &nbRelations);
   for (int relation = 0; relation < nbRelations; relation++)
      scanf("%d%d", &relations[relation][0], &relations[relation][1]);

   // pour afficher un entier :
   printf("%d", X);
   return 0;
}
Squelette de code Caml :
let scan_int () = Scanf.scanf " %d" (fun x -> x)
let show_int x = Printf.printf "%d\n" x

let mon_id = scan_int()
let nb_relations = scan_int()
let relations = Array.init nb_relations (fun _ -> 
    let id1 = scan_int() in
    let id2 = scan_int() in
    (id1,id2)
 (* relations est un tableau de type : array (int * int) *)

let _ = 

   (* pour afficher un entier *)
   show_int x

Source : http://www.france-ioi.org/ Créé par : Arthur Charguéraud et Mathias Hiron.