Pisca-piscas são sempre a maior diversão! Em tempos de festa, eles trazem uma decoração diferente, alegre e que enche o ambiente de amor e esperança. Eles vêm em diversos tamanhos, tipos e cores. Abaixo temos um belo exemplo de pisca-pisca.

Uma empresa que fabrica este produto está passando por alguma dificuldade para a produção de uma encomenda personalizada, feita por uma grande rede de shoppings. Eles pediram muitos, mas muitos quilômetros de pisca-pisca, que devem ser mais emaranhados do que o produto que a empresa normalmente fabrica (eles só fazem o do tipo em linha reta).

No pedido recebido, o artista do shopping descreveu todas as lâmpadas, cores e conexões entre lâmpadas, de forma que o pisca-pisca tivesse a forma e o efeito desejado. Dependendo da configuração, os fios podem formar um ciclo nas conexões. O problema é que o processo com que a empresa liga os fios desse ciclo acaba criando um circuito elétrico de muito baixa resistência: um curto-circuito. A consequência é que as lâmpadas ligadas nesse ciclo se queimam.

Vamos ver um exemplo na figura abaixo. Se a lâmpada 0 for ligada a uma fonte de energia, então todas as lâmpadas serão energizadas, com exceção da lâmpada 7. Observe que existe um ciclo entre as lâmpadas 2, 4 e 6 e outro entre as lâmpadas 1, 8 e 9, o que faz com que essas seis lâmpadas se queimem depois de pouco tempo. Depois que se queimam, as lâmpadas impedem a passagem de energia, de forma que apenas as lâmpadas 0 e 3 vão permanecer acessas, enquanto que a lâmpada 5 se apaga.

Antes de produzir cada pisca-pisca encomendado — e correr o risco de queimar lâmpadas desnecessariamente, a empresa irá verificar cada encomenda recebida. Se houver lâmpadas queimadas ou que não se acendem, então a empresa solicitará ajustes para o artista do shopping. Mas, como o período de festas já está logo ali, é importante já retirar do estoque e começar a ligar as lâmpadas que já sabemos que se acendem. Por isso, é importante listar as lâmpadas do pisca-pisca em ordem de distância para a fonte de energia.

Escreva um programa piscapisca que receba uma encomenda para criar um pisca-pisca e verifica o estado de cada lâmpada energizada na configuração.

Entrada

A primeira linha da entrada contém o número de lâmpadas da encomenda, $n$; o número de conexões diretas entre lâmpadas, $m$; e o identificador da lâmpada que será ligada à fonte de energia, $s$. Cada lâmpada será identificada por um inteiro entre $0$ e $n-1$. Cada uma das $m$ linhas seguintes contém os identificadores de duas lâmpadas ligadas diretamente.

10 10 0
0 3
1 5
1 8
1 9
2 3
2 4
2 6
4 6
5 6
8 9

Saída

Para cada lâmpada do pisca-pisca que foi energizada, em ordem de distância da lâmpada ligada à fonte de energia, deverá ser mostrada a distância e o estado da lâmpada após o pisca-pisca ser ligado, conforme o exemplo. Quando houver empate na distância, as lâmpadas devem ser listadas em ordem de índice.

0 a distancia 0: acesa
3 a distancia 1: acesa
2 a distancia 2: queimada
4 a distancia 3: queimada
6 a distancia 3: queimada
5 a distancia 4: apagada
1 a distancia 5: queimada
8 a distancia 6: queimada
9 a distancia 6: queimada

Dicas

Como pode haver vários vértices com a mesma distância, é preciso ordená-los antes de listá-los na saída. Uma maneira de fazer isso é guardar todos os vértices com a mesma distância em uma estrutura intermediária (e.g., um vetor), ordená-la, e só depois listar os vértices. Mas podemos evitar esse passo se tomarmos um cuidado ao implementar a busca em largura: basta inserir os vértices na fila em ordem crescente.

Para saber se uma lâmpada queimará ou não, é necessário descobrir se ela está em algum ciclo. Há várias formas de fazer isso, algumas mais rápidas, outras mais lentas. Nesta tarefa, não se preocupe em encontrar a melhor maneira possível.

Talvez seja útil desenhar alguns grafos no papel. Ou, se você preferir, utilizar alguma ferramenta pra isso. Experimente colar a lista de arestas aqui.

Critérios

O pisca-pisca deverá ser representado como um grafo utilizando a representação de sua preferência. Para percorrer os vértices em ordem de distância, é obrigatório implementar busca em largura.

Submissão

Você pode fazer esta tarefa individualmente ou em dupla! O objetivo é que vocês tenham a oportunidade de projetar algoritmos e escrever programas em pares. Assim vocês podem trocar ideias e se ajudar mutuamente. Caso queira fazer esta tarefa em dupla, então siga algumas regrinhas:

1. Antes de começar a tarefa, converse e combine com um@ colega. Amb@s devem colaborar ativamente em todos os momentos da elaboração desta tarefa, incluindo ideias, projeto do algoritmo e escrita do código. Não é permitido dividir as atividades para cada um fazer uma parte separadamente.

2. Apenas um estudante deve submeter a tarefa e solicitar a correção aos monitores, mas ambos devem editar o arquivo de configuração dupla.txt fornecido no repositório para indicar o RA da dupla. O monitor corrigirá o código apenas do repositório do RA indicado nesse arquivo e registrará a nota para os dois estudantes no sistema.

3. Tome cuidado para que sua dupla tenha acesso apenas aos arquivos desta tarefa. É proibido compartilhar ou mostrar arquivos de outras tarefas com a dupla, ou quaisquer arquivos das tarefas com terceiros. Vocês sempre podem pedir ajuda a monitor@s!

Se você preferir fazer esta tarefa individualmente, então edite o arquivo dupla.txt para que ele contenha apenas seu RA.

← Anterior Voltar Próximo →