Trouver le sommet le plus lourd dans un graphe
Étant donné un graphe non orienté avec
v sommets et e arêtes, vous devez déterminer le sommet le plus “lourd”. La « lourdeur » d’un sommet est mesurée par son nombre de connexions : plus un sommet a de voisins, plus il est considéré comme lourd. Si plusieurs sommets présentent la même lourdeur maximale, il faut renvoyer celui qui a le numéro le plus petit.Entrée
La première ligne de l’entrée contient deux entiers
v (1 ≤ v ≤ 1000) et e (1 ≤ e ≤ 100 000).Les
e lignes suivantes contiennent chacune une paire 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 l’indice le plus petit du sommet ayant la lourdeur la plus élevée.
Exemples
Entrée | Sortie |
8 9
1 4
4 6
3 2
2 1
5 2
5 6
8 5
7 6
7 8 | 2 |
Explication
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB