Solução Informática - Nível Avançado - Semana 32

Escrito por Arthur Lobo

Conhecimento prévio necessário:

• Busca em Grafos

O problema nos pede algo bem simples: o tamanho do menor ciclo presente no grafo; mas na hora de construirmos uma solução podemos acabar indo pelo caminho errado, já que ele possui várias ideias que parecem certas mas na verdade tem algum erro. Na solução correta, primeiro vamos resolver um problema mais simples: dado uma aresta $(a,b)$ que está no grafo, qual o menor ciclo que passa por essa aresta?

O ciclo vai ser constituído por 2 formas (caminhos) de ir de $a$ até $b$ que não compartilham nenhuma aresta. Um deles é feito somente pela aresta $(a,b)$; o outro é um caminho de $a$ até $b$ que não usa a aresta $(a,b)$ (já que ela foi usada no primeiro caminho).

Portanto, o tamanho desse ciclo é a quantidade de arestas no "caminho 1" (que é 1) + a quantidade de arestas no "caminho 2". Queremos que o "caminho 2" tenha o menor número de arestas, então já que ele não pode ter a aresta $(a,b)$. basta removermos essa aresta e utilizar uma $bfs$ para saber o menor caminho de $a$ até $b$ sem a aresta $(a,b)$.

Então podemos, para cada aresta $(a_i,b_i)$ presente no grafo, saber qual é o menor ciclo que contém ela removendo a aresta $(a_i,b_i)$ e calculando a menor distância de $a_i$ até $b_i$ sem a aresta, e o tamanho desse ciclo será 1 + $distancia(a_i,b_i)$. A complexidade é $O(N+M)$ para cada aresta, então no total fica $O(M*(N+M))$.

Para entender o porquê de essa solução sempre computa o menor ciclo, é só ver que para qualquer aresta que está presente no menor ciclo, a resposta ao calcular o menor ciclo que passa por essa aresta é exatamente o tamanho do menor ciclo.

Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.