LeetCode 1319 Number of Operations to Make Network Connected - Example and Complexity Analysis

Trace n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]].

$5$ cables, need $5$ minimum for $6$ computers. We have exactly enough.

Union operations: union(0,1), union(0,2), union(0,3), union(1,2) [already same], union(1,3) [already same].

After processing: {0,1,2,3} form one component. {4} alone. {5} alone.

Components: $3$.

Operations needed: $3 - 1 = 2$. Move $2$ redundant cables to connect computers 4 and 5.

$O(m \cdot \alpha(n))$ time for $m$ edges. $O(n)$ space.