Retirer le sommet du graphe
On dispose d’un graphe non orienté ayant
v sommets et e arêtes, et l’on souhaite afficher « l’importance » de chaque sommet. Pour chaque sommet, il faut donc enlever toutes les arêtes qui lui sont reliées, puis afficher la matrice d’adjacence après cette suppression. Notez que l’importance de chaque sommet doit être évaluée indépendamment : la suppression de certaines arêtes pour un sommet n’affecte pas les arêtes liées à un autre.Entrée
La première ligne d’entrée contient deux entiers
v (1 ≤ v ≤ 50) et e (1 ≤ e ≤ 200).Les
e lignes suivantes fournissent les paires d’entiers v1, v2 (1 ≤ v1, v2 ≤ v), indiquant que le sommet v1 est connecté au sommet v2.Sortie
Le programme doit afficher
v matrices d’adjacence, chacune séparée par une ligne vide. Chaque matrice représente la connectivité du graphe après la suppression du sommet correspondant. Les matrices doivent être affichées dans l’ordre des numéros de sommets.Exemples
Input | Output |
3 3
1 2
2 3
3 1 | 0 0 0
0 0 1
0 1 0
0 0 1
0 0 0
1 0 0
0 1 0
1 0 0
0 0 0 |
Explication
# La matrice d’adjacence initiale
0 1 1
1 0 1
1 1 0
# Après avoir supprimé le sommet 1
0 0 0
0 0 1
0 1 0
# Après avoir supprimé le sommet 2
0 0 1
0 0 0
1 0 0
# Après avoir supprimé le sommet 3
0 1 0
1 0 0
0 0 0Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB