El link del problema es el siguiente:
1056 – Degrees of Separation
El problema es de Grafos.
Dado un grafo, nos piden revisar dos condiciones:
1.- EL grafo es desconectado
2.- Si no lo es, cual es la ruta mas larga que une a cualesquiera dos nodos
Para la representación del grafo, es recomendable una matriz de adyacencia, ya que el grafo es de a lo mas 50×50.
Para la manipulación de la entrada, es recomendable usar un mapa de un String con un Entero (map<string,int>), con el cual fácilmente a cada nombre le podemos asociar un numero.
Una vez representado el grafo en la matriz de adyacencia, procedemos a utilizar el algoritmo de Floyd Warshall.
Este algoritmo tiene complejidad n^3, pero debido a que el grafo es pequeño, se puede utilizar el algoritmo y obtener una respuesta en el tiempo limite.
Una vez ejecutado el algoritmo de Floyd Warshall, procedemos a buscar el numero mas grande de la matriz resultante.
Si el numero mas grande es igual a Infinito, tenemos que el grafo es desconectado, si no, procedemos a imprimir el numero obtenido.
Otro enfoque diferente, es utilizar una búsqueda por amplitud (BFS).
Para obtener la distancia, lo que hacemos es elegir un nodo aleatorio del grafo y ejecutamos el algoritmo.
Una vez ejecutado, nosotros conocemos la distancia de el nodo elegido hacia todos los demás. Si alguno tiene distancia igual a Infinito, entonces el grafo es desconectado.
Si no, procedemos a ejecutar nuevamente un BFS desde el nodo mas lejano obtenido de la primera búsqueda en profundidad, y sobre los resultados obtenidos, obtener la distancia mas larga.
Este problema básicamente consiste en encontrar lo que se le conoce como diámetro de un Grafo.
Hay un teorema que menciona el hecho que se esta utilizando acá. Si se elige un nodo aleatorio y se realiza una búsqueda en profundidad y elegimos a su vecino mas lejano y realizamos nuevamente una búsqueda en profundidad a partir del nodo obtenido anteriormente, obtendremos el diámetro del Grafo.
Jorge Rodriguez Blog 
Deja un comentario