Union-Find / Disjoint Set

parent[]

rank[]

Default

Active

Path to Root

Root

Merged

Cycle

Time

O(E·α(N))

Space

O(N)

Debugger · v1.0

LIVE

1function hasCycle(edges):

2 for (u, v) in edges:

3 rootU = find(u)

4 rootV = find(v)

5 if rootU == rootV:

6 return True # CYCLE!

7 union(u, v)

8 return False # No cycle

Debugger · v1.0

LIVE

1function hasCycle(edges):

2 for (u, v) in edges:

3 rootU = find(u)

4 rootV = find(v)

5 if rootU == rootV:

6 return True # CYCLE!

7 union(u, v)

8 return False # No cycle

State Inspector

No variables in scope.

Preset:

Union-Find / DSU Visualizer

Cycle Detection via DSU

Step 1 of 5

DSU can detect cycles in an undirected graph in O(E·α(N)). When adding edge (u, v), if Find(u) == Find(v) they are already connected — adding this edge would create a cycle.

Core Insight

An undirected edge (u, v) creates a cycle if and only if u and v are already in the same component (same root). This is because there already exists a path between them.

find(u) ≠ find(v)

→ Safe — add edge, run union

find(u) == find(v)

→ CYCLE! — edge would close a loop