Problema A -
Hasse Diagram
Autor: Fábio Marques (Universidade de Aveiro)
Tipo de problema: Grafos (Pesquisa em Profundidade / Ordenação Topológica)
Número de ficheiros de teste: 10
Este problema divide-se em vários outros sub-problemas.
- Leitura: Embora participantes em concursos não devem ter
dificuldades nisto, a verdade é que a leitura era mais complicada
que normal, uma vez que o número de elementos na mesma linha não era
dado (tokenizer).
- Descobrir as ligações do diagrama: Era necessário perceber
quais as ligações que estavam presentes no diagrama. Como fazer
isso? Supondo que sabem fazer o
contido(A,B) (os
números estão ordenados no conjunto),
então existe ligação entre A e B se não
existir nenhum K tal que contido(A,K)
e contido(K,B), ou seja, se a relação de inclusão é
"directa".
- Descobrir a raíz: A raíz do diagrama é o conjunto que não
está contido em mais nenhum.
- Percorrer o diagrama: Resolver o problema era percorrer
todos o "grafo" criado com as ligações anteriormente criadas,
começando na raíz e escrevendo todo o caminho cada vez que se chega
a uma folha. Mas como escrever os caminhos "ordenados"?
Basta-nos, por exemplo, ordenar os conjuntos no início e fazer a
nossa pesquisa em profundidade pela raíz seguindo os filhos pela
ordem atrás definida!
Em suma, o problema não era difícil, mas era preciso ter cuidado
para ter todos os pequenos passos correctos.
Ligações interessantes: