101
0/320
Loading content...
You are given a network graph that was originally a tree structure (an acyclic connected graph) with n nodes numbered from 1 to n. A tree with n nodes has exactly n-1 edges, ensuring connectivity without any cycles.
However, an additional edge has been mistakenly added to this tree, creating exactly one cycle in the graph. Your task is to identify and return this extra edge that, when removed, would restore the graph back to its original tree structure.
The graph is represented as an array of edges where each element edges[i] = [u, v] indicates an undirected connection between nodes u and v.
Key Observations:
If multiple edges could be removed to restore the tree structure (i.e., multiple edges in the cycle are candidates), return the edge that appears last in the input array.
edges = [[1,2],[1,3],[2,3]][2,3]The original tree had nodes 1-2 and 1-3 connected. The edge [2,3] was added, creating a cycle: 1→2→3→1. Removing [2,3] restores the tree. Since [2,3] is the last edge in the cycle appearing in the input, we return it.
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]][1,4]The graph forms a cycle: 1→2→3→4→1. The edge [1,5] is a branch that doesn't participate in the cycle. Among the cycle edges [1,2], [2,3], [3,4], and [1,4], the edge [1,4] appears last in the input array, so we return it.
edges = [[1,2],[2,3],[3,4],[1,4]][1,4]This graph consists of exactly 4 nodes forming a single cycle. The edge [1,4] is the last edge in the input that is part of the cycle, so removing it breaks the cycle and leaves a valid tree with nodes connected as 1-2-3-4.
Constraints