Trouver la transpose d’un graphe
Étant donné un graphe orienté avec
v sommets et e arêtes, l’objectif est de trouver sa transpose.La transpose d’un graphe orienté s’obtient en inversant la direction de toutes ses arêtes. Autrement dit, c’est un graphe dans lequel toutes les arêtes orientées du graphe initial sont inversées.
La transpose d’un graphe est particulièrement utile pour déceler les chemins inverses ou les relations inversées dans le graphe. Nous en verrons certaines applications plus tard dans ce cours.
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 connecté au sommet v2.Sortie
Le programme doit imprimer la liste d’adjacence du graphe complémentaire. Chaque ligne doit commencer par l’identifiant d’un sommet suivi d’un point-virgule (
:), puis de ses connexions. Les connexions sur chaque ligne doivent être séparées par un espace. L’ordre des sommets et l’ordre des connexions peuvent être arbitraires.Exemples
Entrée | Sortie |
4 4
1 2
1 4
2 4
3 4 | 1:
2: 1
3:
4: 1 2 3 |
Constraints
Time limit: 3.5 seconds
Memory limit: 512 MB
Output limit: 1 MB