Liste d'adjacence - Représentation d'un graphe
Une des manières les plus populaires de représenter un graphe consiste à recourir aux listes d'adjacence. Une liste d'adjacence permet de représenter un graphe sous forme d’un tableau de listes. Chaque élément de ce tableau correspond à un sommet du graphe, et la liste associée à ce sommet contient les sommets qui lui sont adjacents.
Étant donné le graphe orienté illustré dans l'image, nous pouvons obtenir sa liste d'adjacence :
g = [
[], # Nous ignorons le sommet 0
[2, 4], # Sommet 1
[5], # Sommet 2
[2], # Sommet 3
[], # Sommet 4
[6, 8], # Sommet 5
[4, 7], # Sommet 6
[8], # Sommet 7
[5], # Sommet 8
]
Comme vous pouvez le constater, la représentation du graphe avec une liste d'adjacence est bien plus compacte qu’une matrice d'adjacence. Cela s’explique par le fait que notre graphe ne contient pas beaucoup d'arêtes. Dans certains cas, lorsque le nombre d'arêtes devient suffisamment grand, il peut être plus efficace de stocker le graphe sous forme de matrice d'adjacence.
Défi : Des arêtes à la liste d'adjacence
Étant donné un graphe non orienté comptant
v sommets et e arêtes, vous êtes invité à produire sa liste d'adjacence.Entrée
La première ligne de l’entrée contient deux entiers
v (1 ≤ v ≤ 100 000) et e (1 ≤ e ≤ 100 000).Les
e lignes suivantes contiennent des paires d’entiers v1, v2 (1 ≤ v1, v2 ≤ v) indiquant que le sommet v1 est relié au sommet v2 et inversement.Sortie
Le programme doit afficher la liste d’adjacence du graphe donné. Chaque ligne doit commencer par l’identifiant d’un sommet, suivi d’un point-virgule (
:), puis de ses connexions. Les connexions apparaissant sur chaque ligne doivent être séparées par un espace. L’ordre des sommets et celui de leurs connexions peuvent être arbitraires.Exemples
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 |
Explication
Constraints
Time limit: 2.2 seconds
Memory limit: 512 MB
Output limit: 1 MB