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 vértices possui arestas. Portanto, se nosso grafo tivesse apenas uma componente conexa com vértices e arestas, a resposta seria . 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 é , se temos 2 a resposta é , e assim vai. Dessa maneira, se tivermos componentes, a resposta será .
Para conferir o código, clique aqui.