Redundant Connection
You are given an undirected graph that started as a tree with one extra edge added. Your task is to return the redundant edge whose removal makes the graph a tree again.
The redundant edge is the edge that creates a cycle in the graph.
Return the edge whose removal restores the tree structure.
Examples
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Explanation: Removing edge [2,3] restores the tree.
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Explanation: Removing edge [1,4] removes the cycle.
Input: edges = [[1,2],[2,3],[3,1]]
Output: [3,1]
Explanation: The last edge completes the cycle.
Constraints
- 2 = Number of nodes = 1000
- Number of edges = Number of nodes
- 1 = u, v = Number of nodes
Companies
Topics
Solution.cs C#JavaPythonC++Javascript
Unlock the code editor
Sign in to write, run, and submit your solution against the full test suite.
- Run code against sample & hidden test cases
- Save submissions and track your streak
- Compare with editorial & community solutions