Redundant Connection (DSU)

Problem

A graph started as a tree with n nodes and one extra edge was added, creating exactly one cycle. edges lists [u, v] pairs in the order added.

Return the edge that can be removed to restore a tree. If several answers exist, return the one appearing last in the input.

Hint

The first edge whose endpoints are already connected is the redundant one.

case 1

in: [[[1,2],[1,3],[2,3]]]

expected: [2,3]

case 2

in: [[[1,2],[2,3],[3,4],[1,4],[1,5]]]

expected: [1,4]

case 3

in: [[[1,2],[1,2]]]

expected: [1,2]

case 4

in: [[[1,2],[2,3],[1,3],[3,4]]]

expected: [1,3]

Starter codePython

def redundant_connection(edges):
    # Your code here
    pass

4 test cases · run your code against them in the editor