Problem overview
A tree is a connected, undirected graph with no cycle. You start with a tree of n nodes numbered 1 to n, and one extra edge is added between two nodes that weren't joined before. The method findRedundantConnection receives the result as edges, a vector<vector<int>> with n pairs, and returns an edge whose removal leaves a tree. When 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], but removing it would cut node 5 off, so it doesn't count. Of the four edges on the cycle, [1,4] comes last, and the answer is [1,4].
The statement asks for about O(n · alpha(n)) time, where alpha is the inverse Ackermann function, and O(n) extra space.
Approach: add the edges in order with union-find
A slow way is to try the edges from the last one back, remove each and check with a search whether the rest is still connected. That costs O(n^2).
Union-find does better. It keeps the nodes in groups, and each group is a small tree of parent pointers whose root names the group. Adding the edges one by one in the given order, each edge either joins two different groups or has both ends in the same group. If both ends are already in the same group, they were already connected through earlier edges, so this edge closes a cycle.
The graph has exactly one cycle. Removing any edge of the cycle leaves a tree, while removing an edge that is not on the cycle cuts the tree in two. The cycle closes when the last of its edges arrives, because the rest of its edges came earlier. So the first edge that finds both ends in one group is the cycle's last edge, and it is the answer, even when other edges come after it.
Two refinements keep each operation nearly constant. Union by size always hangs the smaller tree under the larger one's root, so trees stay shallow. Path halving makes each node visited while looking for a root point to its grandparent, which shortens later searches.
On the second example the run goes like this:
| Edge | Roots of its ends | What happens |
|---|---|---|
| [1,2] | 1 and 2 | merged; node 1 is the root |
| [2,3] | 1 and 3 | merged |
| [3,4] | 1 and 4 | merged |
| [1,4] | 1 and 1 | same group: returned |
The edge [1,5] is never looked at. In the third example, [[1,2],[3,4],[2,3],[4,5],[1,5]], the edge [2,3] finds the roots 1 and 3: both nodes have been seen, but in two separate groups, so the edge joins them. The edge [1,5] is the one that finds a single root, and it is returned.
Step by step
- Store the edge count in
n. A tree ofnnodes hasn - 1edges, and the extra edge makesn, so the edge count is also the node count. - Create
parentwithn + 1entries. Nodes are numbered from 1, so nodeisits at indexiand index 0 stays unused. - Create
sizewithn + 1entries, all 1. For a rootr,size[r]counts the nodes in its group. - Loop over the indexes from 0 to
ninclusive, - and make every node its own parent. A node that is its own parent is a root, so at the start each node is a group of one.
- Go over the edges in the given order with
auto& edge. The order decides which edge of the cycle is returned. - Find the root of
edge[0]with the helperfindand store it inrootA. - Find the root of
edge[1]inrootB. Two nodes are in the same group exactly when they lead to the same root. - Return the edge when the roots are equal. Both ends are already connected through earlier edges, so this one closes the cycle.
- Make
rootAthe larger root. Ifsize[rootA] < size[rootB],swapthem. This is union by size. - Merge:
parent[rootB] = rootAhangs the smaller tree under the larger one's root. - Update the size:
size[rootA] += size[rootB]. The size ofrootBis never read again. - Return
{}after the loop. The input always contains an extra edge, so the loop returns before it ends. The line is there because the method must return a value on every path. - Write
find. It takesparentas avector<int>&and a nodex, and returns the root ofx's group. The reference is needed:findchangesparent, and a copy would be changed instead of the real vector. - Loop while
parent[x] != x. The root is the only node that is its own parent. A loop needs no call stack, however long the walk is. - Halve the path:
parent[x] = parent[parent[x]]makesxpoint to its grandparent. - Move up:
x = parent[x]. Each turn climbs two levels of the old tree. - Return
x, the root.
The solution in C++
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector<int> parent(n + 1);
vector<int> size(n + 1, 1);
for (int i = 0; i <= n; i++) {
parent[i] = i;
}
for (auto& edge : edges) {
int rootA = find(parent, edge[0]);
int rootB = find(parent, edge[1]);
if (rootA == rootB) {
return edge;
}
if (size[rootA] < size[rootB]) {
swap(rootA, rootB);
}
parent[rootB] = rootA;
size[rootA] += size[rootB];
}
return {};
}
int find(vector<int>& parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
};
The C++ details worth a closer look:
vector<int> parent(n + 1). This makesn + 1zeros. The loop then overwrites each with its own index. The second vector,size(n + 1, 1), is filled with 1 directly.auto& edge. The loop variable is a reference to each inner vector, so nothing is copied while looping.return edgethen copies that vector into the returnedvector<int>.return {}. The empty braces build an emptyvector<int>.swap(rootA, rootB). It exchanges the values of the two local variables. It doesn't touch the arrays.findchanges its argumentparenton purpose. The path halving writes into the real vector, which is why the next calls are faster. Changingxonly changes the helper's own copy of the integer.- Index range. With
n + 1entries the largest valid index isn. A vector ofnentries would make nodenan out-of-range access, which is undefined behaviour.
Complexity
Time: O(n · alpha(n)), nearly O(n). Each of the n edges costs two calls to find, and with union by size and path halving each call costs O(alpha(n)) amortized. The inverse Ackermann function alpha is below 5 for any n that fits in a computer.
Space: O(n). The two vectors have n + 1 entries each, and find uses a loop instead of recursion, so it needs no call stack.
Edge cases and common mistakes
- Returning the last edge of the input. It is often not on the cycle. For
[[1,4],[3,4],[1,3],[1,2],[4,5]]the answer is[1,3], but the last edge is[4,5], and removing it would cut node 5 off. - The cycle's edge that comes first in the input. The answer is the cycle's last edge in input order. In example 2 that is
[1,4], not[1,2]. - Edges after the cycle. Edges that come after the one that closes the cycle are never examined, because the method returns at once. That is correct: they cannot change the answer.
- Same node in different groups. An edge between two nodes that have both been seen is not necessarily a cycle. In the third example
[2,3]joins the groups {1,2} and {3,4}. Only equal roots mean a cycle. - Comparing the nodes instead of the roots. The test is
rootA == rootB. Comparingedge[0]withedge[1]would never be true, since the two ends are different nodes. - Forgetting to merge. Without
parent[rootB] = rootAno group ever grows, so no edge can ever find two ends in the same group. - A long chain. For the chain
[1,2], [2,3], ..., [999,1000]followed by[1,1000], the answer is[1,1000]. Union by size keeps the trees shallow even here.
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,4],[3,4],[1,3],[1,2],[4,5]]gives[1,3].[[2,3],[1,2],[1,3]]gives[1,3].
