LeetCode 684 Redundant Connection - Example and Complexity Analysis

Trace edges = [[1,2],[2,3],[3,4],[1,4],[1,5]].

Process [1,2]: find(1) ≠ find(2). Union them. Components: {1,2}, {3}, {4}, {5}.

Process [2,3]: find(2) ≠ find(3). Union. Components: {1,2,3}, {4}, {5}.

Process [3,4]: find(3) ≠ find(4). Union. Components: {1,2,3,4}, {5}.

Process [1,4]: find(1) = find(4). Both in same component! This edge creates a cycle.

Return [1,4].

(We don't even process [1,5] since we found the answer.)

$O(n \cdot \alpha(n))$ time. $O(n)$ space.