Process edges one by one. An edge creates a cycle if both endpoints are already in the same component:
def findRedundantConnection(edges):
n = len(edges)
uf = UnionFind(n + 1) # nodes are 1-indexed
for 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 we process in order and return the first cycle-creating edge, you get the last such edge in the input (as required) because we process all edges.
Time: . Space: .