Medium · Cycle Detection with DSU
Understand → Visualise → Practice.
Edges of a nearly-tree are given in order. Return the first edge whose addition connects vertices already in the same component, or an empty array if none does.
Add edges one by one. If both ends already share a root, this edge creates a cycle and is the redundant one.
Each vertex is its own set.
For edge (a, b), find both roots first.
If the roots are equal, return [a, b]; otherwise union them and continue.
O(e α(e)) time and O(e) space.
Unioning roots before checking equality hides the cycle-forming edge.
Read the full guide first: Union-Find for Dynamic Connectivity.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.