Trouver le complément d’un graphe
Étant donné un graphe non orienté doté de
v sommets et de e arêtes, vous devez en déterminer le complément.Le complément d’un graphe est un graphe qui présente des arêtes entre tous les nœuds qui n’en avaient pas dans le graphe d’origine, tout en n’ayant pas d’arête entre des sommets qui étaient connectés dans le graphe d’origine.
.png?table=block&id=18b2c681-664d-812d-b03c-daf34071103d&cache=v2)
Entrée
La première ligne de l’entrée contient deux entiers
v (1 ≤ v ≤ 500) 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 et inversement.Sortie
Le programme doit afficher 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 de chaque ligne doivent être séparées par un espace. L’ordre des sommets et celui de leurs connexions peuvent être arbitraires.Exemples
Entrée | Sortie |
4 4
1 2
4 2
4 1
3 4 | 1: 3
2: 3
3: 1 2
4: |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB