Union-find (disjoint set union) answers "are u and v already connected?" almost instantly while edges are being added one at a time. That makes it the natural tool for spotting the edge that first closes a cycle.
You are given a graph that started as a tree with n nodes labelled 1 .. n and then had one extra edge added. edges has length n. Return the edge that can be removed so the result is a tree again. If there are several answers, return the one that occurs last in the input.
Examples
Input: edges = [[1, 2], [1, 3], [2, 3]]
Output: [2, 3]
Input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Output: [1, 4]
Constraints
edgesis a tree on the nodes1 .. n(wheren = len(edges)) plus one extra edge; no edge is repeated- Target: nearly O(n) time with path compression (O(n * alpha(n)))
Goals
- Implement union-find with a parent array, path compression and union by size/rank
- Detect a cycle in an undirected graph by noticing a union of two already-connected nodes
- Process edges incrementally instead of rebuilding a graph each time