Data Structures19 sections · 729 units
Open in Course

Problem - Redundant Connection

Detect cycles in graphs

A tree with nn nodes has exactly n1n-1 edges. Given a graph that started as a tree but has one extra edge, find and return that edge. The extra edge creates exactly one cycle.

Return the edge that, if removed, would restore the tree structure. If multiple answers, return the one appearing last in the input.

Example: edges =[[1,2],[1,3],[2,3]]= [[1,2], [1,3], [2,3]] returns [2,3][2,3]. You're performing cycle detection: the redundant edge connects two nodes that are already in the same component. Constraints: nn from 33 to 10001000.