Solução Informática – Nível Iniciante – Semana 30

Escrito por Arthur Lobo

Conhecimento prévio necessário:

• Busca em grafos
• Árvores

O problema pede para removermos o menor número de arestas de modo que o grafo não possua ciclos.

Vamos pensar de maneira mais simples: E se o grafo possuísse apenas uma componente conexa?  Se quisermos fazer com que uma componente conexa não possua ciclos, transformaremos ela numa árvore. E como nós já sabemos, uma árvore com $N$ vértices possui $N-1$ arestas. Portanto, se nosso grafo tivesse apenas uma componente conexa com $N$ vértices e $M$ arestas, a resposta seria $M-(N-1)$. Exemplo do primeiro caso de teste:

Quando temos mais de uma componente conexa, basta somarmos essa resposta para cada uma delas: Para cada componente conexa, contamos quantos vértices e arestas ela tem e somamos a fórmula descrita a cima na resposta.

Porém, podemos fazer isso de maneira mais simples: observe que cada componente faz com que removamos uma aresta a menos, então se temos uma componente, a resposta é $M-N+1$, se temos 2 a resposta é $M-N+2$, e assim vai. Dessa maneira, se tivermos $C$ componentes, a resposta será $M-N+C$.

Para conferir o código, clique aqui.