Rendre le graphe complet
Étant donné un graphe non orienté avec
v sommets et e arêtes, vous devez déterminer quelles sont toutes les arêtes à ajouter pour rendre ce graphe complet.Entrée
La première ligne de l'entrée contient deux entiers
v (1 ≤ v ≤ 500) et e (1 ≤ e ≤ ).Les
e lignes suivantes contiennent chacune une paire d'entiers v1, v2 (1 ≤ v1, v2 ≤ v), qui indiquent la présence d'une arête entre v1 et v2.Sortie
Le programme doit afficher toutes les arêtes à ajouter pour rendre le graphe complet, dans l'ordre lexicographique (en allant du plus petit identifiant de sommet au plus grand). Chaque arête doit être imprimée sur une ligne séparée, et les sommets doivent être séparés par un espace.
Exemples
Entrée | Sortie |
4 3
1 2
2 3
3 1 | 1 4
2 4
3 4 |
Explication
- Le sommet 4 n'était initialement connecté à aucun autre sommet. Il faut donc le relier à l'ensemble des autres sommets.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB