Os suspeitos

Esse é um excelente problema para quem está implementando seus primeiros algoritmos com grafos, mais especificamente com o algoritmo de encontrar componentes conectados.

Você pode estar achando estranho interpretar esse problema como um grafo. Mas vamos analisar o problema mais em detalhes.

No início você só tem um paciente suspeito, que é o paciente 0. Portanto, é por ele que vamos começar a contar os suspeitos. Inicialmente teremos que marcar todos os pacientes do grupo dele como suspeitos. Depois para cada paciente procurar para ver se eles fazem parte de outros grupos e se fizerem, temos que marcá-los também como suspeitos, e assim sucessivamente. Lembrando de tomar o cuidado de não marcar duas vezes.

Dito isso, vamos olhar novamente esse problema sob a perspectiva de um grafo.

Considere cada paciente um vértice. Pacientes de um mesmo grupo estão todos conectados entre si. Para o exemplo de entrada:

100 4

2 1 2

5 10 13 11 12 14

2 0 1

2 99 2

O grafo seria:

Sendo assim, para descobrir quantos suspeitos existem, podemos montar esse grafo e efetuar uma busca em profundidade a partir do nó 0. A quantidade de nós que conseguirmos visitar será a quantidade de suspeitos. No exemplo acima, os nós 10,13,11, 12 e 14 não são alcançáveis a partir do nó 0. Portanto o nosso resultado para esse caso deverá ser 4.

Se você optar por uma lista de adjacências, você terá que se preocupar em montar o grafo. Lembre que se trata de um grafo não-direcionado e, portanto, se você fizer uma conexão de 1 para 0, não esqueça de fazer de 0 para 1. Para esse exemplo a lista de adjacências ficará como abaixo:

Se você não souber como implementar a lista de adjacências, por favor estude o material disponível em: http://bit.ly/1wb3IHH e http://bit.ly/1nNBC3I