Lista de Adjacência - Representação de Grafos
Uma das formas mais populares de representar grafos é através de listas de adjacência. Uma lista de adjacência é uma maneira de representar um grafo como um array de listas. Cada elemento do array representa um vértice do grafo, e a lista associada a esse vértice contém os vértices que lhe são adjacentes.
Dado o grafo dirigido na figura, podemos obter a sua lista de adjacência:
g = [
[], # We skip vertex 0
[2, 4], # Vertex 1
[5], # Vertex 2
[2], # Vertex 3
[], # Vertex 4
[6, 8], # Vertex 5
[4, 7], # Vertex 6
[8], # Vertex 7
[5], # Vertex 8
]
Como pode observar, a representação do grafo por lista de adjacência é bem mais compacta em comparação com a matriz de adjacência. Isto acontece porque não existem assim tantas arestas no nosso grafo. Em alguns casos, quando o número de arestas é suficientemente grande, pode ser mais eficiente armazenar o grafo numa matriz de adjacência.
Desafio: Arestas para Lista de Adjacência
Dado um grafo não dirigido com
v vértices e e arestas, pretende-se obter a sua lista de adjacência.Entrada
A primeira linha da entrada contém dois inteiros
v (1 ≤ v ≤ 100 000) e e (1 ≤ e ≤ 100 000).As
e linhas seguintes contêm pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v), o que significa que o vértice v1 está ligado ao vértice v2 e vice-versa.Saída
O programa deve imprimir a lista de adjacência do grafo dado. Cada linha deve começar com o id de um vértice seguido de dois pontos (
:) e, em seguida, as suas ligações. As ligações em cada linha devem ser separadas por um espaço. A ordem tanto dos vértices como das ligações pode ser arbitrária.Exemplos
Entrada | Saída |
8 9
1 4
4 6
3 2
2 1
5 2
5 6
8 5
7 6
7 8 | 1: 2 4
2: 1 3 5
3: 2
4: 1 6
5: 2 6 8
6: 4 7 5
7: 8 6
8: 5 7 |
Explicação
Constraints
Time limit: 2.2 seconds
Memory limit: 512 MB
Output limit: 1 MB