Lista de Adyacencia - Representación de Grafos
Una de las formas más populares de representar grafos es mediante listas de adyacencia. Una lista de adyacencia consiste en representar un grafo como un arreglo (array) de listas. Cada elemento del arreglo corresponde a un vértice del grafo, y la lista asociada a ese vértice contiene los vértices que son adyacentes a él.
Dado el grafo dirigido de la imagen, podemos obtener su lista de adyacencia:
g = [
[], # Omitimos el vértice 0
[2, 4], # Vértice 1
[5], # Vértice 2
[2], # Vértice 3
[], # Vértice 4
[6, 8], # Vértice 5
[4, 7], # Vértice 6
[8], # Vértice 7
[5], # Vértice 8
]
Como puedes notar, la representación del grafo con una lista de adyacencia es mucho más compacta que con la matriz de adyacencia. Esto se debe a que nuestro grafo no cuenta con tantas aristas. En algunos casos, cuando el número de aristas es suficientemente grande, podría ser más eficiente almacenar el grafo en una matriz de adyacencia.
Desafío: De Aristas a Lista de Adyacencia
Dado un grafo no dirigido con
v vértices y e aristas, se te solicita obtener su lista de adyacencia.Entrada
La primera línea de la entrada contiene dos números enteros
v (1 ≤ v ≤ 100 000) y e (1 ≤ e ≤ 100 000).Las siguientes
e líneas contienen pares de enteros v1, v2 (1 ≤ v1, v2 ≤ v), lo que significa que el vértice v1 está conectado con el vértice v2 y viceversa.Salida
El programa debe imprimir la lista de adyacencia del grafo dado. Cada fila debe comenzar con el id de un vértice seguido de un punto y coma (
:) y luego sus conexiones. Las conexiones de cada fila deben separarse con un espacio. El orden tanto de los vértices como de las conexiones puede ser arbitrario.Ejemplos
Entrada | Salida |
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 |
Explicación
Constraints
Time limit: 2.2 seconds
Memory limit: 512 MB
Output limit: 1 MB