The connection that closes a loop
A tree on nodes 1 to n had one extra edge added between two of its nodes, so
the n edges below contain exactly one cycle. edges[i] = [a, b] is an undirected edge with
a < b.
Return an edge whose removal leaves a tree on all n nodes. If several edges qualify, return the one
that appears last in edges.
Examples
| Input | Output | Why |
|---|---|---|
edges = [[1,2],[1,3],[2,3]] | [2, 3] | Any of the three edges breaks the triangle; [2, 3] comes last. |
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] | [1, 4] | The cycle is 1–2–3–4–1. [1, 5] is not on it. |
edges = [[1,2],[2,3],[1,3],[3,4]] | [1, 3] | The last edge on the cycle, not the last edge overall. |
Constraints
- 3 ≤ n ≤ 1000
- edges.length = n
- 1 ≤ a < b ≤ n; no edge repeats
- The graph is connected
Hints
Hint 1
Add the edges one at a time and keep track of which nodes are already connected.
Hint 2
The first edge whose two ends are already connected closes the cycle.
Hint 3
Why is that also the last cycle edge in the list? Every edge before it was needed to connect something.
Where people lose marks
- Returning the last edge of the whole list rather than the last edge on the cycle.
- Forgetting that nodes are numbered from 1: the parent array needs n + 1 entries.
- A union-find without path compression or union by size, which is O(n) per find on a chain.
Dry run on [[1,2],[2,3],[3,4],[1,4],[1,5]]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5groups5
Every node starts as its own root: n separate groups. An arrow points from a node to its parent.
-
Step 2 / 5groups4
Edge 1–2: roots 1 and 2 differ. Attach the smaller tree (root 2) under the larger (root 1).
-
Step 3 / 5groups3
Edge 2–3: roots 1 and 3 differ. Attach the smaller tree (root 3) under the larger (root 1).
-
Step 4 / 5groups2
Edge 3–4: roots 1 and 4 differ. Attach the smaller tree (root 4) under the larger (root 1).
-
Step 5 / 5groups2
Edge 1–4: find(1) = find(4) = 1. They are already in the same group, so this edge would close a cycle. That is the answer.
How to think about it
Process the edges in order with union-find. While the edges seen so far form a forest, each new edge either joins two different trees (union succeeds) or has both ends in the same tree. The first edge of the second kind closes the only cycle in the graph.
It is also the right edge to return. The cycle consists of that edge and a path made of earlier edges, so every other cycle edge appears before it in the list: it is the last edge on the cycle, which is exactly what the tie rule asks for.
Complexity. Time O(n · α(n)) · Space O(n)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def redundant_edge(edges):
parent = list(range(len(edges) + 1)) # nodes are 1..n
size = [1] * (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] # already connected: this edge closes the cycle
if size[ra] < size[rb]:
ra, rb = rb, ra
parent[rb] = ra # smaller tree under the larger
size[ra] += size[rb]
return []#include <numeric>
#include <utility>
#include <vector>
std::vector<int> solve(const std::vector<std::vector<int>>& edges) {
const int n = edges.size();
std::vector<int> parent(n + 1), size(n + 1, 1); // nodes are 1..n
std::iota(parent.begin(), parent.end(), 0);
auto find = [&](int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } // path halving
return x;
};
for (const auto& e : edges) {
int ra = find(e[0]), rb = find(e[1]);
if (ra == rb) return {e[0], e[1]}; // closes the cycle
if (size[ra] < size[rb]) std::swap(ra, rb);
parent[rb] = ra;
size[ra] += size[rb];
}
return {};
}class Solution {
private int[] parent;
private int find(int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } // path halving
return x;
}
public int[] redundantEdge(int[][] edges) {
int n = edges.length;
parent = new int[n + 1]; // nodes are 1..n
int[] size = new int[n + 1];
for (int i = 0; i <= n; i++) { parent[i] = i; size[i] = 1; }
for (int[] e : edges) {
int ra = find(e[0]), rb = find(e[1]);
if (ra == rb) return new int[]{e[0], e[1]}; // closes the cycle
if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
size[ra] += size[rb];
}
return new int[0];
}
}function redundantEdge(edges) {
const parent = Array.from({ length: edges.length + 1 }, (_, i) => i); // nodes are 1..n
const size = new Array(edges.length + 1).fill(1);
const find = x => {
while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } // path halving
return x;
};
for (const [a, b] of edges) {
let ra = find(a), rb = find(b);
if (ra === rb) return [a, b]; // already connected: closes the cycle
if (size[ra] < size[rb]) [ra, rb] = [rb, ra];
parent[rb] = ra;
size[ra] += size[rb];
}
return [];
}fn solve(edges: &[[i64; 2]]) -> Vec<i64> {
let n = edges.len();
let mut parent: Vec<usize> = (0..=n).collect(); // nodes are 1..n
let mut size = vec![1usize; n + 1];
fn find(parent: &mut Vec<usize>, mut x: usize) -> usize {
while parent[x] != x {
parent[x] = parent[parent[x]]; // path halving
x = parent[x];
}
x
}
for e in edges {
let mut ra = find(&mut parent, e[0] as usize);
let mut rb = find(&mut parent, e[1] as usize);
if ra == rb {
return vec![e[0], e[1]]; // closes the cycle
}
if size[ra] < size[rb] {
std::mem::swap(&mut ra, &mut rb);
}
parent[rb] = ra;
size[ra] += size[rb];
}
Vec::new()
}import qualified Data.Map.Strict as M
solve :: [[Int]] -> [Int]
solve = go M.empty
where
-- parent map: a node absent from the map is its own root (no compression: n <= 1000 keeps it fast)
root p x = case M.lookup x p of
Just y | y /= x -> root p y
_ -> x
go _ [] = []
go p ([a, b] : rest)
| ra == rb = [a, b] -- already connected: closes the cycle
| otherwise = go (M.insert ra rb p) rest
where
ra = root p a
rb = root p bVariants to try
- The graph is directed and was a rooted tree: one extra directed edge was added (a node may now have two parents).
- Return every edge on the cycle.
- Several extra edges were added: return the minimum set of edges to remove (all edges that union-find rejects).
Next problems
Moving cables to connect a network
Count the separate groups with a disjoint-set structure; spare cables are the edges that close a cycle.
Open the problem → Medium25 minConnect every point at the least cost
Join points on a grid with the least total Manhattan distance. Every pair is an edge, so the dense form of Prim's algorithm wins.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem →Write a solution and run it against the real test table.
Keep going
Moving cables to connect a network
Count the separate groups with a disjoint-set structure; spare cables are the edges that close a cycle.
Open the problem → Medium25 minConnect every point at the least cost
Join points on a grid with the least total Manhattan distance. Every pair is an edge, so the dense form of Prim's algorithm wins.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → GraphsThe pattern behind it
Grids, networks and dependencies are all graphs. Breadth-first search finds shortest paths, depth-first search and union-find find what is connected, Dijkstra handles weighted edges, and a queue of nodes with no remaining prerequisites gives an order.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.