684. Redundant Connection

Practice Redundant Connection for free on NudgeCode: Medium, Graph pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

A tree with n nodes labeled 1 to n had one extra edge added, so the graph now has exactly one cycle. edges[i] = [a, b] is an undirected edge. Return an edge whose removal turns the graph back into a tree. If several edges qualify, return the one that appears last in edges.

Example

edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]  ->  [1,4]

Constraints

• 3 <= n <= 1000
• edges.length == n
• 1 <= a < b <= n
• no repeated edges, and the graph is connected