XXVI Olimpíada Brasileira de Informática

Pontes de Dodegônia

O arquipélago Dodegônia é formado por doze lindas ilhas interligadas por várias pontes. Uma propriedade importante para os habitantes de Dodegônia é que, utilizando as pontes, é possível ir de bicicleta de qualquer ilha para qualquer outra ilha, mesmo que para isso seja necessário utilizar mais de uma ponte.

Infelizmente uma tempestade tropical destruiu completamente todas as pontes de Dodegônia e agora o governo precisa iniciar a construção de novas pontes.

Questão 1. Suponha que o governo decida construir o menor número possível de pontes de forma a garantir que, utilizando as pontes, seja possível ir de bicicleta de qualquer ilha para qualquer outra ilha, atravessando uma ou mais pontes. Nesse caso, qual o menor número de pontes que o governo deve construir?
10
11
12
13
14

Questão 2. Suponha que o governo decida construir o menor número possível de pontes de forma a garantir que, utilizando as pontes, seja possível ir de bicicleta de qualquer ilha para qualquer outra ilha atravessando exatamente uma das pontes. Nesse caso, qual o menor número de pontes que o governo deve construir?
58
60
62
64
66

Tarefas Iniciação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação