844. Número de Erdos

Olá meus amigos nerds. Hoje vamos resolver um dos primeiros problemas que me apresentaram a essa vida de resolver problemas. Vamos tentar descobrir qual é nosso número de Erdos, já que é isso que o problema 844. Número de Erdos nos pede para fazer. Mais especificamente, nossa tarefa é determinar, a partir de uma lista de autores de artigos, o número de Erdos dos autores.

Nesse problema, vale a pena até contar mais um pouco de história. O matemático húngaro Paul Erdos (1913-1996), é considerado o matemático mais prolífico da história, devido ao seu alto número de publicações (mais de 1500). Em homenagem a este gênio húngaro, os matemáticos criaram um número, denominado "número de Erdos". Toda pessoa que escreveu um artigo com Erdos tem o número 1. Todos que não possuem número 1, mas escreveram algum artigo juntamente com alguém que possui número 1, possuem número 2. E assim por diante. Quando nenhuma ligação pode ser estabelecida entre Erdos e uma pessoa, diz-se que esta possui número de Erdos infinito. Por exemplo, o número de Erdos de Albert Einstein é 2. E, talvez surpreendentemente, o número de Erdos de Bill Gates é 4.

Solução

Outro problema que a solução é uma busca em largura! Mas por motivos históricos, não resisti a tentação de escrever ele. Dado um grafo onde os vértices representam os autores e existe uma aresta entre dois vértices se os autores publicaram juntos, o tamanho do caminho mínimo entre o cada vértice e o vértice que representa Erdos é o número procurado. Como todas as arestas tem o mesmo peso (o grafo não é ponderado), uma simples busca em largura resolve.

Implementação

Que código feio, mas vocês tem que me perdoar já que ele foi escrito há muitos anos atrás.