Problem overview
A tree is an undirected graph that is connected and has no cycle. The input here is a tree of n nodes, numbered 1 to n, with one extra edge added between two nodes that were not joined before. The graph is given as edges, a Vec<Vec<i32>> of n pairs. The function find_redundant_connection returns an edge that can be removed so that the remaining n - 1 edges form a tree again. If several edges work, it returns the one that comes last in edges.
For [[1, 2], [1, 3], [2, 3]] the three edges form the cycle 1 - 2 - 3 - 1. Removing any of them leaves a tree, and [2, 3] comes last, so that is the answer. For [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] the cycle is 1 - 2 - 3 - 4 - 1. The edge [1, 5] comes after [1, 4] in the input, but removing it would cut node 5 off from the others, so it is not an option. Of the four edges on the cycle, [1, 4] comes last, and the answer is [1, 4].
The statement sets a budget of nearly O(n) time, written O(n * alpha(n)), and O(n) extra space.
Approach: add edges one by one with union-find
A brute-force approach tries each edge from the last back, removes it, and runs a depth-first search to see whether the rest is still connected. That is O(n^2).
The faster idea is to add the edges in the order they are given and keep the nodes in groups. An edge whose two ends are already in the same group closes a cycle, because there is already a path between them. The graph has exactly one cycle. Removing any edge of that cycle leaves a tree, while removing an edge that is not on it splits the tree in two. All the cycle's edges except the last to arrive came earlier, so the edge that finally closes the cycle is the cycle's last edge in the input, and that is the answer. Edges that come after it do not matter.
The groups are kept with union-find. Each node points to a parent, and the root, the one node that is its own parent, names its group. Two nodes are in the same group exactly when they lead to the same root. Two refinements keep the trees shallow:
- Union by size. When two groups merge, the smaller tree goes under the larger one.
- Path halving. While climbing to the root, each node is pointed at its grandparent, so later climbs are shorter.
Together they make each step cost O(alpha(n)) amortized, where alpha is the inverse Ackermann function, which stays below 5 for any n a computer can hold.
Here is the algorithm on [[1, 2], [3, 4], [2, 3], [4, 5], [1, 5]]. The list after each edge is parent for nodes 1 to 5:
edge [1, 2]: roots 1 and 2 -> parent[2] = 1, parent = [1, 1, 3, 4, 5]
edge [3, 4]: roots 3 and 4 -> parent[4] = 3, parent = [1, 1, 3, 3, 5]
edge [2, 3]: roots 1 and 3 -> parent[3] = 1, parent = [1, 1, 1, 3, 5]
edge [4, 5]: roots 1 and 5 -> parent[5] = 1, parent = [1, 1, 1, 1, 1]
edge [1, 5]: roots 1 and 1 -> same group, cycle
When [2, 3] arrives, nodes 2 and 3 are both known, but in two separate groups, {1, 2} and {3, 4}: the edge joins them. The last edge finds both ends under the root 1, so it closes the cycle and is returned.
Step by step
- Store the edge count in
n. A tree ofnnodes hasn - 1edges, and the extra one makesn, so this is also the number of nodes. - Create
parentas aVec<usize>holding0, 1, ..., n, by collecting the range0..=n. Every node starts as its own parent. Nodes are numbered from 1, so the vector hasn + 1entries and index 0 is never used. - Create
sizeasvec![1; n + 1]. For a rootr,size[r]counts the nodes in its group. - Loop over
&edges, in the given order. The order decides which edge of the cycle comes out. - Find the root of
edge[0]withSelf::find(&mut parent, edge[0] as usize)and keep it in a mutableroot_a. The edge holdsi32values, soas usizeturns them into indexes. - Find the root of
edge[1]the same way, inroot_b. - Detect the cycle. If
root_a == root_b, the ends are already connected through earlier edges, so this edge closes the cycle. Returnedge.clone(), a vector of its own. - Apply union by size. If
size[root_a] < size[root_b], swap the two roots withstd::mem::swap, soroot_ais the root of the larger group. - Merge: set
parent[root_b]toroot_a. - Update the size: add
size[root_b]tosize[root_a]. - Fall back to an empty vector after the loop. The input always contains an extra edge, so the loop returns before it ends, but a function must return a value on every path.
- Write
find. It takesparent: &mut Vec<usize>andmut x: usizeand returns the root ofx's group. - Climb with a
whileloop that runs whileparent[x] != x, so it stops at the root. - Halve the path: set
parent[x]toparent[parent[x]], so the node skips a level. - Move up: set
xtoparent[x], which is now the old grandparent. - Return
xas the last expression: it is the root.
The solution in Rust
impl Solution {
fn find_redundant_connection(edges: Vec<Vec<i32>>) -> Vec<i32> {
let n = edges.len();
let mut parent: Vec<usize> = (0..=n).collect();
let mut size = vec![1; n + 1];
for edge in &edges {
let mut root_a = Self::find(&mut parent, edge[0] as usize);
let mut root_b = Self::find(&mut parent, edge[1] as usize);
if root_a == root_b {
return edge.clone();
}
if size[root_a] < size[root_b] {
std::mem::swap(&mut root_a, &mut root_b);
}
parent[root_b] = root_a;
size[root_a] += size[root_b];
}
Vec::new()
}
fn find(parent: &mut Vec<usize>, mut x: usize) -> usize {
while parent[x] != x {
parent[x] = parent[parent[x]];
x = parent[x];
}
x
}
}
The Rust details worth a closer look:
(0..=n).collect(). The range includesn, so it holdsn + 1numbers. The type written onparenttellscollect()to build aVec<usize>.- Type of
size.vec![1; n + 1]has no type annotation, and nothing forces a particular integer type, so the counts arei32by default. They are only compared and added, never used as indexes, so that is fine. &mut parent. Each call tofindlends the vector mutably, because path halving writes into it. The borrow ends when the call returns, so the next call can borrow it again.mut x. It makes the parameter itself mutable, so the loop can move it up the tree. It changes onlyfind's own copy of the number.- Iterating
&edges. The loop borrows the vector, soedgeis a&Vec<i32>. Returning it needsedge.clone()to make a vector the function owns. std::mem::swap. It takes two mutable borrows and exchanges the values behind them. That is whyroot_aandroot_bare declaredmut.- Casting with
as usize. The node numbers are positive, so the cast is exact here. A negativei32would wrap to a huge number instead of failing. - No recursion in
find. The loop needs no call stack, however long the chain is. On a path of 1000 nodes with the edge[1, 1000]added at the end, the function returns[1, 1000].
Complexity
Time: O(n * alpha(n)), nearly O(n). Each of the n edges costs two calls to find, each O(alpha(n)) amortized with union by size and path halving, plus constant work for the merge.
Space: O(n). The parent and size vectors have n + 1 entries each.
Edge cases and common mistakes
- The last edge in the input is not always the answer. On
[[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]the last edge is[1, 5], but the answer is[1, 4]. The same happens on[[1, 2], [2, 3], [1, 3], [3, 4]], where the answer is[1, 3]and the input ends with[3, 4]. - The cycle's closing edge need not touch the first edge. In
[[1, 2], [1, 3], [1, 4], [3, 4]]the cycle is 1 - 3 - 4 - 1, and the answer is[3, 4]. - Index 0. Nodes start at 1, so both vectors have
n + 1entries. Building them with onlynentries would make nodenan out-of-bounds index. - Comparing the nodes instead of the roots. The test must compare
findresults. Two nodes in the same group usually differ as numbers. - Starting a second search from the removed edge. No second pass is needed: the first edge that closes a cycle is already the answer.
Testing
[[1, 2], [1, 3], [2, 3]]gives[2, 3].[[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]gives[1, 4].[[1, 2], [3, 4], [2, 3], [4, 5], [1, 5]]gives[1, 5].[[1, 2], [2, 3], [1, 3], [3, 4]]gives[1, 3].[[1, 2], [1, 3], [1, 4], [3, 4]]gives[3, 4].
