LeetMotion
You are given a tree with n nodes labelled from 1 to n, and one additional edge that was added to the tree. The graph is represented as an array of edges where edges[i] = [ai, bi].
Return the edge that, if removed, would turn the graph back into a tree. If there are multiple valid answers, return the last one in the input.
find(u) and find(v). If they return the same root, they're already in the same component — adding this edge would create a cycle.find(x), point every node along the path directly to the root. Combine with union by rank (attach the shorter tree under the taller) for nearly O(1) amortized operations.A company is laying network cables to connect n offices. A proper spanning tree requires exactly n−1 cables. One day a technician accidentally adds an extra cable between two offices that were already reachable — creating a redundant loop in the network (which causes broadcast storms in Ethernet). Union-Find is exactly how modern network management software detects these loops in O(n·α(n)) time during topology discovery.
For every edge, temporarily remove it and check if the remaining graph is still connected (DFS/BFS). The last edge whose removal keeps the graph connected is the answer.
[u, v] from the graph.n nodes are reachable, this edge was redundant.Why it's slow: O(n) edges × O(n) DFS per removal = O(n²). Union-Find solves this in a single forward pass.
def findRedundantConnection(edges): n = len(edges) for i in range(n - 1, -1, -1): u, v = edges[i] adj = [[] for _ in range(n + 1)] for j, (a, b) in enumerate(edges): if j != i: adj[a].append(b); adj[b].append(a) seen = set() def dfs(x): seen.add(x) for nb in adj[x]: if nb not in seen: dfs(nb) dfs(1) if len(seen) == n: return [u, v]
Process edges one by one. Before merging, check if both endpoints already share a root. If yes — this edge creates a cycle and is redundant.
parent[i] = i for every node.[u, v], call find(u) and find(v) (with path compression).[u, v].
Discussion
…