quinta-feira, 11 de junho de 2015

Maratona de Programação - Problema URI 1790

Olá pessoal, nesse post irei discutir um problema de maratona de programação que eu elaborei para o URI. O problema se chama Detectando Pontes ou Detecting Bridges.

Link para o problema:


O intuito do post é explicar o problema para que você possa tentar resolvê-lo. Trata-se de um problema relativamente fácil, logo você percebe que se trata de um problema que envolve grafos.

O problema fornece a quantidade de cidades "C" e a quantidade de pontes (bridges) "P". A quantidade de cidades é o número de vértices do grafo e a quantidade de pontes é o número de arestas.

Não existem cidades (vértices) isoladas e nenhuma ponte (aresta) é inserida mais de uma vez.

O problema pede que você forneça como saída o número de pontes (número de arestas) que não estão contidas em qualquer ciclo.

Não confundir as pontes (arestas) que interconectam as cidades (vértices) com o conceito de pontes de um grafo.

O conceito de pontes em teoria dos grafos é: ponte é uma aresta que não está contida em qualquer ciclo.

Claramente temos um grafo não direcionado, pois se uma ponte liga as cidades A e B, isso quer dizer que há um caminho de A para B assim como um caminho de B para A.

Para você detectar se uma aresta é uma ponte, basta remover essa aresta do grafo e verificar se o grafo continua conectado (lembre-se que nesse problema TODAS as cidades estão interligadas). Um grafo não direcionado é conectado se ele tem exatamente um componente conectado.

Se não aumentou o número de componentes do grafo, então a aresta em questão (aresta removida) não é uma ponte. Após fazer essa verificação, coloque a aresta novamente no grafo. Faça isso para todas as arestas para contar quantas pontes existem no grafo.

Para verificar se o grafo não direcionado permanece conectado após a remoção de uma determinada aresta, você pode fazer uma DFS (busca em profundidade), se essa DFS visitar todos os vértices então o grafo continua conectado, caso contrário a aresta removida é uma ponte.

Quaisquer dúvidas deixem nos comentários, até a próxima!


Nenhum comentário: