First Cycle Edge via Union-Find

Problem

Process undirected edges in order and report the first one that closes a cycle.

Maintain a union-find structure; an edge [u, v] creates a cycle when u and v already share a root. Return that edge exactly as given, or an empty list when the graph stays a forest. Assume no self-loops appear before a repeated connection.

Hint

An edge is redundant exactly when its two endpoints already have the same root.

Test cases

case 1

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

expected: [2,0]

case 2

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

expected: []

case 3

in: [4,[[0,1],[0,1]]]

expected: [0,1]

case 4

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

expected: [4,0]

Starter codePython

def first_cycle_edge(n, edges):
    # Your code here
    pass

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