3203. Trouver le diamètre minimum après la fusion de deux arbres

3203. Trouver le diamètre minimum après la fusion de deux arbres

Difficulté : Difficile

Sujets :Arbre,Recherche en profondeur d'abord,Recherche en largeur d'abord,Graphique

Il existe deux arbres non orientés avecnetmnœuds, numérotés à partir de0àn-1et de0àm-1, respectivement. Vous recevez deux tableaux d'entiers 2Dbords1etbords2de longueursn-1etm-1, respectivement, oùbords1[i] = [ai, bi]indique qu'il y a un bord entre les nœudsaietbidans le premier arbre etbords2[i] = [ui, vi]indique qu'il y a un bord entre les nœudsinterface utilisateuretvidans le deuxième arbre.

Vous devez connecter un nœud du premier arbre avec un autre nœud du deuxième arbre avec une arête.

Renvoie le diamètre minimum possible de l'arbre résultant.

Le diamètre d'un arbre est la longueur du chemin le plus long entre deux nœuds quelconques de l'arbre.

Exemple 1 :

• Entrée : bords1 = [[0,1],[0,2],[0,3]], bords2 = [[0,1]]
• Sortie : 3
• Explication : On peut obtenir un arbre de diamètre 3 en connectant le nœud 0 du premier arbre avec n'importe quel nœud du deuxième arbre.

Exemple 2 :

• Entrée : bords1 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]], bords2 = [[0,1...
  [Courte citation de 8% de l'article original]