172. Redundant Connection

Medium · Graph

In a graph with n nodes labeled 1 to n, there is exactly one additional edge that creates a cycle. Find and return that redundant edge.

You are given an array of edges where each edge is represented as [u, v], indicating a connection between nodes u and v. The graph is initially a tree (n-1 edges for n nodes), and adding one more edge creates exactly one cycle.

Return the edge that, if removed, would make the graph a tree again. If multiple edges could be removed to achieve this, return the one that appears last in the input array.

Examples

Example 1
Input: edges = [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The graph has 3 nodes and 3 edges. Nodes 1, 2, and 3 form a cycle. The edge [2,3] is the last edge that creates the cycle, so it is the redundant connection.
Example 2
Input: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The graph has 5 nodes. Edges [1,2], [2,3], [3,4], [1,4] form a cycle. The edge [1,4] is the last edge in the cycle, so it is redundant.

Constraints