Problema C - Where could we meet?

Autor: Vasco Manquinho (Instituto Superior Técnico)
Tipo de problema: Grafos
Número de ficheiros de teste: 15

Este era, para mim, um dos problemas mais interessantes da MIUP. Era pegar numa "velha" tarefa tantas veves feita, mas dar-lhe o toque adicional de desta vez ter de ser feito de forma muito eficiente, uma vez que o limite de 1,000,000 nós e ligações impedia aproximações "primitivas".

Antes de continuar, deixem-me dizer que o problema geral subjacente é o da descoberta do Fecho Transitivo de um grafo (ou seja, de onde se pode chegar a onde. O algoritmo mais conhecido para isso é o Floyd-Warshall, que necessita de uma matriz de adjacências e gasta O(N^3) em termos temporais. Mas nada disto se aplica com os limites que temos, claro... Em compensação, o problema é mais simples um pouco, no sentido em que apenas queremos conhecer aqueles a qual se pode chegar a partir de todos os outros.

Existiam várias maneiras de fazer este problema, mas irei descrever agora a maneira como fiz que tem a particularidade de correr em O(V+E), ou seja, é linear para este problema.

Primeiro, tive em conta o grafo invertido (ou seja, se havia ligação a->b, passa a existir antes a b->a). Desde modo, o problema passa a ser descobrir o número de nós a partir dos quais se consegue chegar a todos os outros.

Em segundo lugar usei o algoritmo de Tarjan que descobre os "Componenes Fortemente Ligados" (CFL). O que é isto? Os CFL são conjuntos maximais de nós, entre os quais se consegue chegar qualquer um a qualquer outro. Por exemplo:

Se descobrir todos os CFL, então posso reduzir e construir um novo grafo condensado onde cada novo nó é um CFL. Este grafo tem a importantíssima particularidade de ser acíclico!.

Finalmente, se descobrir um CFL de onde se chegue a todos os outros no grafo condensado, então a resposta que quero é o tamanho (em número de nós) desse CFL. E como descobrir? Basta-me ver quais são os CFL sem nenhuma ligação para si (o primeiro numa ordenação topológica, portanto). Pode no entanto existirem vários desdes CFL candidatos:
- Podemos fazer uma pesquisa em profundidade a partir de cada um deles e ver se chega a todos os outros, ou...
- Basta ver se apenas existe um "único candidato possível". Se tal acontecer, garantidamente dele se chega a todos os outros! Conseguem perceber porquê?

Logo, para resolver é só detectar os CFL em O(V+E) e a seguir descobrir se apenas existe um CFL sem ligações para si no grafo condensado em O(V+E), novamente.

Ligações interessantes: