IF672 -
Algoritmos e Estruturas de Dados
novembro 2002
a março 2003
3 - Componentes Conexos
Achar
os componentes conexos do grafo.
Um componente conexo é
um conjunto de vértices de um grafo G dado, tal que cada um deles seja alcançável a partir de outro, todos pertencentes
a esse conjunto.
Um vértice v e w são conexos se existe algum caminho que vai de v a w. Um
grafo é conexos se para cada v e w do grafo, v e w são conexos.
Entrada e Saída de dados
A entrada consiste em várias
conjuntos
de dados.
Cada conjunto começa com um
valor (N < 30) indicando a quantidade de nós no grafo direcionado.
Segue N linhas cada uma com a lista de adjacência correspondente ao nó i (i-ézima
linha).
O final da linha de
adjacência termina com 0.
Fim de arquivo indica o final da entrada.
A saída consiste da impressão de cada componente conexo em uma linha só
separados por espaço ' '.
Um componente deve ser impresso da seguinte maneira:
{x1,x2,x3...,xn} com x1
< x2 < x3.. < xn e x1,x2,..,xn
pertencentes ao componente.
Olhe a saída exemplo para mais detalhes.
Entrada exemplo
5
2 4 3 0
1 0
4 5 0
1 3 0
1 2 3 4 0
3
2 3 0
1 3 0
1 2 0
6
2 3 0
1 4 0
1 2 4 0
1 2 3 0
6 0
5 0
9
8 0
6 0
7 0
6 0
8 0
2 4 8 0
3 0
1 5 6 0
9 0
Saída correspondente
{1,2,4,3,5}
{1,2,3}
{1,2,3,4} {5,6}
{1,2,4,5,6,8} {3,7} {9}