Problema 2
Los Amigos de mis Amigos
amigos.pas, amigos.c, amigos.cpp
El Popochas tiene varios cuates, lo que quiere saber es cuántos amigos tienen en común dos de ellos. La teoría de la amistad del Popochas es la siguiente:
1) A siempre es amigo de A.
2) Si A dice que B es su amigo, y B dice que C es su amigo, entonces A dice que C es su amigo.
3) Si A dice que B es su amigo, no necesariamente B dice que A es su amigo.
Problema
Dado un número la cantidad de amigos (n) y la relación de amistad entre ellos, dar la cantidad de amigos comunes entre un par de ellos.
Entrada
La primera línea tendrá dos números n y m, 1 ≤ n ≤ 100, 1 ≤ m ≤ 10000, la cantidad de amigos y la cantidad de relación de amistad entre ellos respectivamente. Cada uno de los siguientes m renglones tendrá dos números entre 1 y n, (a, b) lo cual significará a dice que b es su amigo. El último renglón tendrá dos números (p y q), para los cuales hay que obtener los amigos comunes entre ellos.
Salida
Un único número, la cantidad de amigos comunes entre p y q.
Observación: Las relaciones personales son muy difíciles, por lo cual, que q sea amigo p, no significa que p sea amigo de q, aunque uno siempre es amigo de si mismo.
Ejemplo
entrada | salida |
3 2 1 2 3 2 1 3 |
1 |
4 4 4 1 3 1 1 2 2 3 3 1 |
3 |
Concurso: | 11a OMI, Aguascalientes - Examen de Selección. 23/Abril/2006 |
Propuesto por: | Óscar Dávalos Orozco |
Ayuda: | entradas, salidas, sugerencias |
Soluciones: | amigos.pas, amigos.c, amigos.cpp |