A tree with n nodes (labelled 1..n) had one extra edge added. Given the list of edges, return an edge that can be removed so the graph becomes a tree again. If there are several answers, return the one that appears last in the input.
edges = [[1,2],[1,3],[2,3]][2,3]edges = [[1,2],[2,3],[3,4],[1,4],[1,5]][1,4]parent[i] = i ๐(u, v): find both roots, flattening the path on the wayunion: hang the lower-rank root under the higher-rank onePath compression points every node on a find path straight at the root, so the next find is one hop. Union by rank always hangs the shorter tree under the taller one, so trees stay flat. Together, each operation costs about ฮฑ(n), the inverse Ackermann function, which is โค 4 for any realistic n. That's effectively constant.
Nodes are 1-indexed, so size the arrays n + 1. The input is guaranteed to be a tree plus exactly one extra edge, so the first edge that joins two nodes already in the same group is the one that appears last among the cycle's edges, which is exactly what's asked. The same pattern solves "Number of Provinces" and "Graph Valid Tree".
You could remove each edge in turn and check whether the rest is a tree. That repeats a full graph search for every edge.
Process the edges in order with union find. At the start, every node is its own group. For each edge, find the root of both ends. If the roots differ, merge the two groups. If the roots are already equal, the two nodes were already connected, so this edge forms the cycle, and it is the answer.
An edge whose ends already share a root closes a cycle. Union find answers connectivity questions almost in constant time.
Run the animation above on your own input, or watch the 1:45 video explanation of Redundant Connection with a dry run and Java code.