LeetCode 684 Redundant Connection - Logic

Loop through the input edges. For every edge [u, v]:

$1.$ Check find(u) and find(v).

$2.$ If they are the same, this edge creates a cycle. Return it.

$3.$ Otherwise, union(u, v) and continue.

The problem guarantees exactly one redundant edge, so you will always find it. Return the last edge that would form a cycle. Time: $O(n \cdot \alpha(n)) \approx O(n)$. Space: $O(n)$ for the parent and rank arrays.