Process edges one by one. An edge creates a cycle if both endpoints are already in the same component:
function findRedundantConnection(edges):
n = edges.length
uf = new UnionFind(n + 1) // nodes are 1-indexed
for each (u, v) in edges:
if not uf.union(u, v):
return [u, v] // already connected = cycle
return []
The insight: in a tree, every edge connects two previously disconnected nodes. The edge that connects two nodes in the same component is the extra edge.
Since the graph is a tree plus one extra edge, exactly one edge will fail the union. That edge is the redundant one.
Time: . Space: .