Redundant Connection
Description
Given a graph that started as a tree with n nodes and one additional edge added, return an edge that can be removed so the graph becomes a tree.
Examples
edges = [[1,2],[1,3],[2,3]][2,3]Removing [2,3] makes it a valid tree.
edges = [[1,2],[2,3],[3,4],[4,1]][4,1]The edges form a cycle: 1-2-3-4-1. Since processing edges in order and the last edge [4,1] completes the cycle by connecting node 4 back to node 1 (which are already connected through the path 4-3-2-1), removing [4,1] breaks the cycle and creates a valid tree.
edges = [[2,3],[1,2],[1,3],[4,1],[5,4]][1,3]After processing [2,3] and [1,2], there are a path 3-2-1. When encountering [1,3], it creates a cycle because nodes 1 and 3 are already connected through the path 1-2-3. Removing [1,3] eliminates the redundant connection while keeping all nodes connected in a tree structure.
Constraints
- •
n == edges.length - •
3 ≤ n ≤ 1000 - •
1 ≤ ai < bi ≤ n
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.