O município de Águas Molhadas é formado por várias vilas interligadas por igarapés. Os igarapés funcionam como sistema viário, já que a maioria dos habitantes usa barcos como meio de transporte. Os igarapés têm uma forte corrente, o que obriga os barcos a transitarem todos no mesmo sentido em cada igarapé (na verdade, é proibido o trânsito de barcos na contra-mão). A prefeitura do município mantém um único Posto de Saúde e um barco-ambulância utilizado para transporte de doentes.
O timoneiro do barco-ambulância está sempre com pressa, e tem medo de confundir-se no emaranhado de igarapés quando atende um chamado para buscar um doente em alguma vila. Por isso, ele deseja uma lista de todos os possíveis caminhos entre a vila onde se encontra o Posto de Saúde e cada outra vila do município.
Sete vilas interligadas por onze igarapés com mão única
Tarefa
Sua tarefa é escrever um programa que liste todos os caminhos que partem da vila onde se encontra o Posto de Saúde até cada outra vila do município, de forma que em cada caminho nenhuma vila é repetida. As vilas são numeradas de 1 a N, sendo que a vila onde se encontra o Posto de Saúde será sempre a de número 1.
Entrada
A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém um número inteiro N que indica a quantidade de vilas do município. As linhas seguintes contêm, cada uma, dois inteiros positivos X e Y que indicam que a vila X tem um igarapé que a liga diretamente com a vila Y, sem passar por outras vilas, com o trânsito fluindo na direção de X para Y. O final da lista de igarapés é indicado por X = 0 e Y = 0. O final da entrada é indicado por N = 0.
Exemplo de Entrada
2
1 2
2 1
0 0
7
1 2
2 6
7 4
7 1
4 5
4 3
3 4
6 4
6 7
6 2
5 7
0 0
0
Saída
Para cada conjunto de teste da entrada seu programa deve produzir um conjunto de saída com uma lista de caminhos. A primeira linha de um conjunto de saída deve conter o identificador do conjunto, no formato "Teste n", onde n é numerado a partir de 1. As linhas seguintes devem conter os caminhos, ordenados lexicograficamente. Cada caminho é composto de uma seqüência de identificadores de vilas separados por um ou mais espaços em branco. A última linha de um conjunto de saída deve ser deixada em branco.
Exemplo de Saída
Teste 1
1 2
Teste 2
1 2
1 2 6
1 2 6 4
1 2 6 4 3
1 2 6 4 5
1 2 6 4 5 7
1 2 6 7
1 2 6 7 4
1 2 6 7 4 3
1 2 6 7 4 5
(esta saída corresponde ao exemplo de entrada acima)
Restrições
0 ≤ N ≤ 100 (N = 0 apenas para indicar o final da entrada)
1 ≤ Y ≤ N
1 ≤ X ≤ N
ALGORITMOS E IMPLEMENTAÇÕES ⇒ Problema com grafos Tópico resolvido
Moderador: [ Moderadores TTB ]
Abr 2012
26
17:34
Problema com grafos
"É melhor lançar-se à luta em busca do triunfo,mesmo expondo-se ao insucesso,do que ficar na fila dos pobres de espírito,que nem gozam muito nem sofrem muito,por viverem nessa penumbra cinzenta de não conhecer vitória e nem derrota" F. Roosevelt
Jun 2012
09
18:54
Re: Problema com grafos
up
"É melhor lançar-se à luta em busca do triunfo,mesmo expondo-se ao insucesso,do que ficar na fila dos pobres de espírito,que nem gozam muito nem sofrem muito,por viverem nessa penumbra cinzenta de não conhecer vitória e nem derrota" F. Roosevelt
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 0 Respostas
- 246 Exibições
-
Última msg por Lucastadeu14
-
- 1 Respostas
- 226 Exibições
-
Última msg por Idocrase
-
- 0 Respostas
- 181 Exibições
-
Última msg por Thiagosn1
-
- 1 Respostas
- 491 Exibições
-
Última msg por geobson