Detect Cycle in Undirected Graph via DSU

Problem

Detect whether an undirected graph contains a cycle using union-find.

Nodes are numbered 0 to n-1 and edges is a list of [u, v] pairs. Union the endpoints of each edge; if an edge connects two nodes that already share a root, a cycle exists.

Return True if the graph has a cycle, otherwise False. Self-loops and parallel edges count as cycles.

Hint

An edge whose endpoints are already connected closes a cycle.

Test cases

case 1

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

expected: true

case 2

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

expected: false

case 3

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

expected: true

case 4

in: [1,[]]

expected: false

Starter codePython

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

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