Trabalho - Componentes Conexas

Prévia do material em texto

Primeiro trabalho de grafos 2013.1
O governo do planeta Môrica resolveu ler/ouvir todos os emails, cartas, telefonemas, etc de seus
cidadãos. O conceito pode nos parecer alienígena, visto que não possuímos algo parecido na Terra, e
certamente nos rebelaríamos caso algo assim ocorresse estabelendo um novo tipo de governo  com
maior transparência, mas lá há um motivo nobre para a vigilância: os téRRRistes (embole a língua no
R), um povo meio excêntrico que vive nos desertos, está atacando as pessoas!
O problema dos  téRRRistes com os  outros  môricanos  é  que, para  os primeiros, todos devem
atravessar portas pulando na ponta do pé e dançar a macarena ao pôr­do­sol, mas os outros pulam na
ponta do pé somente ao entrar em algum lugar e dançam a macarena ao nascer do sol, sendo que alguns
descrentes se recusam até mesmo de seguir estas tradições. O medo dos  téRRRistes  é compreensível
pois não seguir os rituais pode trazer 7 anos de azar para todos... Quer dizer, ninguém chegou a provar
cientificamente que o azar realmente ocorre, mas talvez isso seja explicado pelo azar dos cientistas do
planeta, todos não seguidores dos rituais.
 
Os môricanos, no entanto, não possuem conhecimentos científicos para analisar os dados que
coletam diariamente. Assim, você foi escolhido, em nome da Federação de Planetas, para uma missão
diplomática  que   consiste   em  implementar   uma   solução   que   os   ajude   na   busca   de   téRRRistes
demonstrando a nossa boa fé.
Especificações
Dada uma lista de mensagens entre môricanos, é necessário identificar os possíveis conjuntos de
téRRRistes, considerando o seguinte:
1. TéRRRistes não enviam mensagens para outros môricanos.
2. TéRRRistes são muito unidos e dados dois téRRRistes a e b quaisquer sempre existe
alguma  sequência  de   téRRRistes   t1, t2, t3, ... ,t k tal  que   t i envia  uma  mensagem
para  t i+1 , a=t1 e  b=t k .
Entrada
A entrada do programa, que deve ser lida da entrada padrão, tem na primeira linha dois números
N e M, onde N é o número de môricanos e M o de mensagens.
Cada uma das próximas M linhas possui dois inteiros A e B, significando que uma mensagem 
foi transmitida do cidadão A para o cidadão B.  1⩽A⩽N ,   1⩽B⩽N e A≠B . Não haverão 
dois pares ordenados (A, B) iguais. Note que pode haver, por exemplo, (1, 3) e (3, 1) na mesma lista 
visto que o par ordenado (1, 3) é diferente do par (3, 1).
Saída
A saída deve ser transmitida na saída padrão.
Cada conjunto possível de téRRRistes  deve ser colocado em uma linha.  Para representá­lo,
escreva uma lista separada de espaço em ordem crescente dos cidadãos.
Além disso,   as   linhas  devem ser  dispostas   em ordem crescente   conforme  seus   respectivos
conjuntos.  Consideraremos  que um conjunto   S1 é  menor  que um conjunto   S 2 sse   S1≠S 2 e
min {(S1−S2)∪(S2−S1)}∈S1 .
Exemplos
Entrada Saída Explicação
2 1
1 2
2 2   não   mandou   mensagem
alguma,   mas   1   mandou   uma
provavelmente  por   engano   para
2, assim somente 2 pode ser um
téRRRiste.
3 3
1 2
2 3
3 1
1 2 3 Todas as três pessoas conversam
entre   si...   Assim   a   única
possibilidade  é  de  todos   serem
téRRRistes!
3 2
1 2
1 3
2
3
1 não pode ser téRRRiste, 2 e 3
podem,  mas  2   e   3  não   enviam
mensagens   um   para   o   outro,
assim   existem   somente   dois
conjuntos possíveis {2} e {3}.
4 4
1 3
1 2
2 4
4 2
2 4
3
1   não   pode   ser   téRRRiste   pois
ele se comunica com 3 sem ser
correspondido,  mas   3   pode   ser
téRRRiste.
2   e   4   comunicam­se   entre   si,
então   ambos   podem   ser
téRRRistes,   apesar   de   não
poderem em separado.
Assim   existem   dois   conjuntos
possíveis {2, 4} e {3}.
Restrições
• Entrega até dia 11 de agosto através do SVN da disciplina 
http://disciplinas.dcc.ufba.br/viewvc/MATA53/ 
• Serão   aceitos   trabalhos   em   quaisquer   linguagens  que   leiam/escrevam  da/na  entrada/saída
padrão. Se a linguagem for especialmente obscura, indicações de como compilar/executar o
código serão apreciadas.
• Os trabalhos receberão até 85% da nota se retornarem a resposta de todo o primeiro grupo de 
entradas (aproximadamente 5000) em até 10 seg. Todas as entradas do primeiro grupo terão
N⩽10 .
• Os 15% restantes da nota serão dados para o segundo grupo com aproximdamente 5 entradas e 
N⩽100000 e  M⩽500000 . Dica: em vez de recursão tente usar iteração (ou seja, loop).
	Primeiro trabalho de grafos 2013.1
	Especificações
	Entrada
	Saída
	Exemplos
	Restrições