A fabric inventory started as a spanning tree: n routers, n - 1 cables. A change ticket added one backup link. On-call now needs the last extra cable in the change log — pull that one, the mesh is a tree again. The intern added each cable to an adjacency list, walked for a cycle, rolled the cable back when the walk closed. A dozen routers in staging returned in milliseconds. A thousand-node fabric in production was still walking after every insert when the request timed out.
Redundant Connection asks for the extra undirected edge that turns a tree into one cycle — the last such edge in the input, which is the first pair already in the same set. This is Number of Provinces inverted: that prompt unions every road and counts leftover roots. Here the graph started as a tree plus one extra edge, and the first failed union is the cable to pull.
This is an interview writeup, not a layout lecture. The graphs post owns adjacency list versus matrix. The union-find post owns path compression and rank. Here we only union each edge until two ends already share a root.
The problem
There are n nodes labeled 1 through n, and n undirected edges. The graph is a tree plus one extra edge. Return that extra edge. If several cycle edges could be removed, return the one that appears last in the input — the edge that completes the cycle when you process in order.
edges = [[1, 2], [1, 3], [2, 3]] → [2, 3]
edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] → [1, 4]First: three nodes, the triangle closes on [2, 3]. Second: 1-2-3-4 is a path until [1, 4] closes the cycle; [1, 5] never gets the chance to be extra.
Note: Removing any cycle edge restores a tree. The prompt wants the last one in the input. Union-Find does that without naming the cycle: earlier cycle edges merge as if they were tree edges.
Adding each edge and DFS-hunting a cycle is the honest brute force
Build an adjacency list. For each edge, add both directions, walk from one end with a parent so the reverse undirected hop is not a cycle, and if a seen neighbor appears, this edge closed a loop — roll it back and return it. Correct. Quadratic.
int[] findRedundantConnectionBrute(int[][] edges) {
int n = edges.length;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<>());
}
for (int[] e : edges) {
int a = e[0];
int b = e[1];
adj.get(a).add(b);
adj.get(b).add(a);
boolean[] seen = new boolean[n + 1];
if (hasCycle(adj, a, -1, seen)) {
adj.get(a).remove(adj.get(a).size() - 1);
adj.get(b).remove(adj.get(b).size() - 1);
return e;
}
}
throw new IllegalArgumentException("no extra edge");
}
boolean hasCycle(List<List<Integer>> adj, int node, int parent, boolean[] seen) {
seen[node] = true;
for (int nei : adj.get(node)) {
if (nei == parent) {
continue;
}
if (seen[nei] || hasCycle(adj, nei, node, seen)) {
return true;
}
}
return false;
}At n = 4 this is a rounding error. On n cables you restart an n-node walk n times: you paid a full DFS per edge for a question that only needs one find per end.
Union until the ends already share a root
One parent array of length n + 1 — nodes are 1 … n, so skip index 0. Each node starts as its own root. Process edges in order. If find(a) and find(b) differ, hang one root under the other. Same root already — that edge is extra; return it. Flatten-on-find and rank live in the union-find post; do not re-lecture them at this board unless they ask.
[[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
parent 1 2 3 4 5
(1,2) different union 1 under 2 parent[1]=2
(2,3) different union 2 under 3 parent[2]=3
(3,4) different union 3 under 4 parent[3]=4
(1,4) find(1)=4, find(4)=4 same → [1, 4]No neighbor list. The Java is that scan; union returns whether a merge happened so a failed merge can return the edge.
int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
int[] parent = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
for (int[] e : edges) {
if (!union(parent, e[0], e[1])) {
return e;
}
}
throw new IllegalArgumentException("no extra edge");
}
int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
boolean union(int[] parent, int a, int b) {
int ra = find(parent, a);
int rb = find(parent, b);
if (ra == rb) {
return false;
}
parent[ra] = rb;
return true;
}Time is O(n α(n)) — one find per endpoint, nearly constant. Space is O(n) for parent (and the find call stack). A parent-aware DFS after each add is the brute above, not a second default.
Note: Nodes are 1-indexed. parent must be length n + 1. A 0-based array of length n drops node n. Do not DFS the finished graph and return an arbitrary back edge; that can be an earlier cycle edge, and the prompt asked for the last one in the input.
What interviewers usually poke next
- DFS / BFS cycle hunt. Parent-aware walk so the reverse undirected hop is not a cycle. Same answer if you add in order and return the first closing edge. Iterative flood uses an
ArrayDeque, notjava.util.Stack. Keep Union-Find as the default board; the walk is the follow-up. - Number of Provinces. Same
parentarray. There you union every road and count leftover roots. Here the firstfind(a) == find(b)is the answer you return. - Min Cost to Connect All Points. Kruskal on sorted candidate edges: skip if already connected, else union and add the cost. Same skip; there the skip is not in the MST, here the skip is the extra edge.
- Redundant Connection II. A directed graph with one extra arc is a different case split (two parents, a cycle, or both) and is out of scope here.
- Rank, or a read-only find. The union-find post owns those tweaks. Name them; do not derive them here unless they ask.
n = 3already a triangle. The last input edge is extra. The prompt promises a tree plus one edge, so a solution exists.
You are done with this problem when you can say, out loud, why adding each edge and DFS-hunting a cycle is correct, why the last extra edge in the input is the first same-set pair, and why leftover-root counting is a different question on the same structure.