Lista di Adiacenza - Rappresentazione di un Grafo
Uno dei modi più comuni per rappresentare un grafo è tramite le liste di adiacenza. Una lista di adiacenza è un metodo che utilizza un array di liste per descrivere un grafo. Ogni elemento dell’array rappresenta un vertice del grafo e la lista associata a quel vertice contiene i vertici a esso adiacenti.
Dato il grafo diretto nell’immagine, possiamo ricavare la sua lista di adiacenza:
g = [
[], # Saltiamo il vertice 0
[2, 4], # Vertice 1
[5], # Vertice 2
[2], # Vertice 3
[], # Vertice 4
[6, 8], # Vertice 5
[4, 7], # Vertice 6
[8], # Vertice 7
[5], # Vertice 8
]
Come si può notare, la rappresentazione del grafo con una lista di adiacenza risulta molto più compatta rispetto alla matrice di adiacenza. Ciò accade perché nel nostro grafo non sono presenti molti archi. In alcuni casi, quando il numero di archi è sufficientemente elevato, potrebbe essere più efficiente memorizzare il grafo in una matrice di adiacenza.
Sfida: Archi in Lista di Adiacenza
Dato un grafo non orientato con
v vertici e e archi, si richiede di ricavarne la lista di adiacenza.Input
La prima riga dell’input contiene due interi
v (1 ≤ v ≤ 100 000) ed e (1 ≤ e ≤ 100 000).Le
e righe successive contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v) che indicano che il vertice v1 è collegato al vertice v2 e viceversa.Output
Il programma deve stampare la lista di adiacenza del grafo dato. Ogni riga deve iniziare con l’id di un vertice seguito da un punto e virgola (
:) e poi le sue connessioni. Le connessioni in ogni riga devono essere separate da uno spazio. L’ordine sia dei vertici sia delle connessioni può essere arbitrario.Esempi
Input | Output |
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 |
Spiegazione
Constraints
Time limit: 2.2 seconds
Memory limit: 512 MB
Output limit: 1 MB