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.
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.
Vous devez afficher un entier sur une ligne : le nombre d'amis d'amis qui ne sont pas des amis directs.
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
#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