Redundant Connection
Problem statement
A rack has n switches labelled 1 to n. They were cabled as a tree: every switch reachable from every other, with no loops. Then someone plugged in exactly one extra cable, which created a loop.
You get the cable list edges, where each [a, b] is an undirected cable between switches a and b. Return the cable that can be unplugged so the network is a tree again. If more than one cable would work (every cable on the loop would), return the one that appears last in edges.
There are no duplicate cables and no cable connects a switch to itself.
Examples
Example 1
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1, 4]
Explanation: The loop is 1-2-3-4-1. Any of its four cables could go, and [1,4] is the last of them in the list.
Example 2
Input: edges = [[1,2],[1,3],[3,4],[2,4],[4,5]]
Output: [2, 4]
Explanation: The loop is 1-2-4-3-1, and [2,4] is the last loop cable listed.
Hints
Approach
Union-find (disjoint set union). Give every switch a parent pointer, initially itself. find(x) follows parents to the root of x's group; union(a, b) links the two roots.
For each cable [a, b] in order, compare find(a) and find(b). If they are equal, a and b are already in the same group, so this cable is the redundant one. Otherwise merge the groups.
Two tricks keep the trees flat: path compression (point nodes closer to the root while you walk) and union by rank (attach the shorter tree under the taller one). Together they make each operation effectively constant time.
O(n · α(n))Space O(n)def find_redundant_connection(edges): parent = list(range(len(edges) + 1)) rank = [0] * (len(edges) + 1) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # path halving x = parent[x] return x for a, b in edges: ra, rb = find(a), find(b) if ra == rb: return [a, b] if rank[ra] < rank[rb]: ra, rb = rb, ra parent[rb] = ra if rank[ra] == rank[rb]: rank[ra] += 1 return [] print(find_redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]))print(find_redundant_connection([[1, 2], [1, 3], [3, 4], [2, 4], [4, 5]]))Follow-up questions
- What if the cables are directed, so the result must be a rooted tree where every node has one parent? (Redundant Connection II: also check for a node with two parents.)
- Count the number of separate networks after all cables are added (union-find: count roots).
Frequently asked questions
A loop in a layer-2 network is a real outage (a broadcast storm), and spanning-tree protocols exist to break exactly this kind of loop. More generally, union-find is the tool for "which of these hosts, services or clusters are connected?" when links arrive over time, and this is the smallest problem that tests it.
A loop cannot exist until every cable on it has been added. So the moment find(a) == find(b) first happens, the cable you are holding is the final piece of the loop, which means every other loop cable came earlier in the list.
It is the inverse Ackermann function, which grows so slowly that it is below 5 for any input that fits in memory. In practice, union-find with path compression and union by rank is treated as constant time per operation.