684. Connexion redondante

684. Connexion redondante

Difficulté: moyen

Sujets:Recherche en profondeur d'abord,Recherche de largeur,Union Find,Graphique

Dans ce problème, un arbre est un graphique non dirigé qui est connecté et n'a pas de cycles.

On vous donne un graphique qui a commencé comme un arbre avecnnœuds étiquetés à partir de1àn, avec un bord supplémentaire ajouté. Le bord ajouté a deux sommets différents choisis parmi1àn, et n'était pas un bord qui existait déjà. Le graphique est représenté comme un tableaubordsde longueurnoùbords [i] = [ai, bi]indique qu'il y a un bord entre les nœudsIAetbidans le graphique.

Retourner un bord qui peut être supprimé afin que le graphique résultant soit un arbre dennœuds. S'il y a plusieurs réponses, renvoyez la réponse qui se produit en dernier dans l'entrée.

Exemple 1:

• Entrée: bords = [[1,2], [1,3], [2,3]]
• Sortie: [2,3]

Exemple 2:

• Entrée: bords = [[1,2], [2,3], [3,4], [1,4], [1,5]]
• Sortie: [1,4]

Contraintes:

• n == EDGES.
• 3 <= n <= 1000
• bords [i] .length == 2
• 1 <= Ai <Bi <= bords.Length
• ai! = bi
• Il n'y a pas d'arêtes répétées.
• L...
  [Courte citation de 8% de l'article original]