Trouver le diamètre d’un arbre
Vous disposez d’un arbre contenant
v sommets. Votre objectif est de calculer le diamètre de cet arbre. Le diamètre correspond à la longueur du chemin séparant les deux sommets les plus éloignés.Entrée
La première ligne de l’entrée contient un entier
v (1 ≤ v ≤ 100 000).Les
v-1 lignes suivantes comportent chacune deux entiers v1, v2 (1 ≤ v1, v2 ≤ v). Cela signifie que le sommet v1 est relié au sommet v2 et inversement.Sortie
Le programme doit afficher le diamètre de l’arbre donné.
Exemples
Entrée | Sortie |
3
1 2
1 3 | 2 |
5
1 2
1 3
3 4
3 5 | 3 |
Indice 1
Vous pouvez réaliser plusieurs DFS (parcours en profondeur) en partant de différentes sources.
Indice 2
Vous pouvez lancer un DFS (parcours en profondeur) depuis le nœud 1 afin de trouver le sommet le plus éloigné (puisqu’il s’agit d’un arbre, donc sans cycles, vous n’avez pas besoin d’effectuer un BFS).
Ensuite, démarrez un autre DFS à partir du sommet ainsi trouvé pour découvrir le sommet qui en est le plus éloigné.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB