Escrito por Arthur Lobo
Conhecimento prévio necessário:
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.