Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ENERGIA - Transmissão de Energia

A distribuição de energia para as diversas regiões do país exige um investimento muito grande em linhas de transmissão e estações transformadoras. Uma linha de transmissão interliga duas estações transformadoras. Uma estação transformadora pode estar interligada a uma ou mais outras estações transformadoras, mas devido ao alto custo não pode haver mais de uma linha de transmissão interligando duas estações.

As estações transformadoras são interconectadas de forma a garantir que a energia possa ser distribuída entre qualquer par de estações. Uma rota de energia entre duas estações e1 e ek é definida como uma sequência (e1 , l1 , e2 , l2 , ...ek−1 , lk−1 , ek ) onde cada ei é uma estação transformadora e cada li é uma linha de transmissão que conecta ei ei+1.

Os engenheiros de manutenção do sistema de transmissão de energia consideram que o sistema está em estado normal se há pelo menos uma rota entre qualquer par de estações, e em estado de falha caso contrário.

Um grande tornado passou pelo país danificando algumas das linhas de transmissão, e os engenheiros de manutenção do sistema de transmissão de energia necessitam de sua ajuda.

Tarefa

Dada a configuração atual do sistema de transmissão de energia, descrevendo as interconexões existentes entre as estações, escreva um programa que determine o estado do sistema.

Entrada

A entrada é composta de vários casos de teste. A primeira linha de um caso de teste contém dois números inteiros E e L indicando respectivamente o número de estações (3 ≤ E ≤ 100) e o número de linhas de transmissão do sistema (E − 1 ≤ L ≤ E × (E − 1)/2) que continuam em funcionamento após o tornado. As estações são identificadas por números de 1 a E. Cada uma das L linhas seguintes contém dois inteiros X e Y que indicam que existe uma linha de transmissão interligando a estação X à estação Y. O final da entrada é indicado por E = L = 0.

A entrada deve ser lida do dispositivo de entrada padrão.

Saída

Para cada caso de teste seu programa deve produzir três linhas na saída. A primeira identifica o conjunto de teste no formato “Teste n”, onde n é numerado a partir de 1. A segunda linha deve conter a palavra “normal”, se, para cada par de estações, houver uma rota que as conecte, e a palavra “falha” caso não haja uma rota entre algum par de estações. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

A saída deve ser escrita no dispositivo de saída padrão.

Exemplos

Entrada:
6 7
1 2
2 3
3 4
4 5
5 6
6 2
1 5
4 3
1 2
4 2
1 4
0 0

Saida:
Teste 1
normal

Teste 2
falha

Restrições

3 <= E <= 100
E − 1 <= L <= E × (E − 1)/2

Adicionado por:Wanderley Guimarăes
Data:2007-03-09
Tempo limite:0.149s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Olimpiada Brasileira de Informatica 2005 Programacao Nivel 2

hide comments
2016-04-21 17:07:56 Elsio [UFABC]
Outros sobre grafos
http://wiki.maratona.dcc.ufmg.br/index.php/Algoritmos_em_Grafos
2016-04-21 17:04:40 Elsio [UFABC]
Monta o grafo e conta as visitas pelo DFS()
o bang ta normal se n de visitas = n de vertices.

Relacionados: (mais dificeis)
http://br.spoj.com/problems/OBIDOMIN/
http://br.spoj.com/problems/GINCAN11/
2015-03-24 13:18:29 Henrik


Last edit: 2015-03-24 13:18:45
2013-03-23 20:29:24 Renato Mariscal
Gabriel, eu acho que é 1s por caso de teste, e o tempo exibido é total de todos casos de testes.
2012-06-25 21:51:02 Gabriel Inácio
tempo limite 1s, estava olhando tem várias submissőes com tempo limite maior que 1s..
2012-06-25 18:55:37 Alan
todos os meus testes fucncionam, so o soj que naoa ceita meu codigo...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.