Redundant Connection
Intermediate
The nodes are numbered 1 to n. The edges list a tree with one extra edge added, so exactly one cycle exists. Return an edge that can be removed so that the rest is a tree. If several edges can be removed, return the one that appears last in edges.
For [[1, 2], [1, 3], [2, 3]] the answer is [2, 3].
Examples
Example 1
Input:
find_redundant_connection([[1, 2], [1, 3], [2, 3]])
Output:
[2, 3]
Example 2
Input:
find_redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]])
Output:
[1, 4]
Constraints
2 <= number of nodes <= 100000len(edges)equals the number of nodes- No other cycle exists apart from the one made by the extra edge.
Theory
Go to TheoryKeywords
dsa-sheetgraphsdisjoint-sets
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.