Problem overview
A tree is a connected graph with no cycle. The graph in this lesson began as a tree of n nodes, numbered from 1 to n, and then one extra edge was added between two nodes that were not joined before. The method findRedundantConnection receives edges, an Array<IntArray> of length n in which each entry [a, b] is an edge between nodes a and b. It returns an edge that can be removed so that the other n - 1 edges form a tree again. When several edges would work, it returns the one that comes last in edges.
For [[1,2],[2,3],[3,4],[1,4],[1,5]] the edges [1,2], [2,3], [3,4] and [1,4] form a cycle through the nodes 1, 2, 3 and 4. Removing any one of them leaves a tree, and [1,4] comes last of the four, so the answer is [1, 4]. The edge [1,5] comes later in the list, but it is not on the cycle: removing it would cut node 5 off.
The statement asks for roughly O(n) time, which rules out removing each edge and testing whether the rest is still connected, a method that costs O(n^2).
Approach: add the edges in order with union-find
Union-find keeps nodes in groups and answers "are these two nodes in the same group?" in almost constant time. Each group is a small tree of parent pointers, and the root, the one node that is its own parent, names the group.
Add the edges one by one, in the given order. Before adding an edge, find the roots of its two ends. If the roots differ, the ends are in separate groups, and the edge merges them. If the roots are equal, the ends are already connected through earlier edges, so this edge closes a cycle.
The graph has exactly one cycle. All the other edges of that cycle come before the one that closes it, so the first edge that finds both ends in the same group is the last edge of the cycle in the input, which is the one to return. Edges that come after it never matter, as the example above shows with [1,5].
Two standard tricks keep the group trees shallow. Union by size hangs the smaller tree under the root of the larger one. Path halving makes each node visited during a search point to its grandparent. Together they make each operation cost O(α(n)) amortized, where α is the inverse Ackermann function, which stays below 5 for any n a computer can hold. In practice that is constant.
Step by step
- Store
nasedges.size. A tree ofnnodes hasn - 1edges, so with the extra one, the edge count is also the node count. - Create
parentas anIntArrayofn + 1entries withparent[i] = i. Every node starts as the root of its own group. Nodes are numbered from 1, so index 0 is never used. - Create
sizeas anIntArrayofn + 1ones. For a rootr,size[r]counts the nodes in its group. - Loop over
edgesin the given order, because that order decides which edge of the cycle is returned. - Find the root of
edge[0]intorootA, declared withvarbecause it may be swapped. - Find the root of
edge[1]intorootBthe same way. - Test for the cycle. If
rootA == rootB, returnedge. - Compare sizes. If
size[rootA] < size[rootB], swap the two roots, so thatrootAis the root of the larger group. - Swap through
temp, so that the first assignment does not lose the old value ofrootA. - Finish the swap:
rootAtakesrootB, thenrootBtakestemp. - Merge by setting
parent[rootB] = rootA. - Update the size:
size[rootA] += size[rootB]. - Return
IntArray(0)after the loop. The input always has an extra edge, so the loop returns first, but the method must return a value on every path. - Write
find, takingparentandnodeand returning anInt. - Copy
nodeintovar x, because Kotlin parameters can't be reassigned. - Loop while
parent[x] != x: whilexis not a root. - Halve the path: set
parent[x]toparent[parent[x]]. - Move up: set
xtoparent[x], the grandparent. - Return
x, the root.
The solution in Kotlin
class Solution {
fun findRedundantConnection(edges: Array<IntArray>): IntArray {
val n = edges.size
val parent = IntArray(n + 1) { it }
val size = IntArray(n + 1) { 1 }
for (edge in edges) {
var rootA = find(parent, edge[0])
var rootB = find(parent, edge[1])
if (rootA == rootB) {
return edge
}
if (size[rootA] < size[rootB]) {
val temp = rootA
rootA = rootB
rootB = temp
}
parent[rootB] = rootA
size[rootA] += size[rootB]
}
return IntArray(0)
}
fun find(parent: IntArray, node: Int): Int {
var x = node
while (parent[x] != x) {
parent[x] = parent[parent[x]]
x = parent[x]
}
return x
}
}
Kotlin details worth knowing:
IntArray(n + 1) { it }builds an array and runs the block once per index. Inside the block,itis the index, so each entry gets its own index as value.IntArray(n + 1) { 1 }fills the array with ones.valandvar.rootAandrootBarevarbecause the swap reassigns them.tempis aval, since it is set once.- Function parameters are read-only. That is why
findcopiesnodeintoxbefore walking up. - Arrays are passed by reference. When
findhalves a path, it changes theparentarray thatfindRedundantConnectionowns. The change is the whole point of path halving. - The returned edge is the input's own array.
return edgegives back the veryIntArraythat was inedges, not a copy. - A loop, not recursion.
findis written with awhileloop, so it needs no call stack however long the walk is.
Tracing the example
Running the solution's steps on [[1,2],[3,4],[2,3],[4,5],[1,5]], printing the roots of each edge and then the parent entries for nodes 1 to 5, gives:
edge [1, 2]: roots 1 and 2 -> merge, parent = [1, 1, 3, 4, 5]
edge [3, 4]: roots 3 and 4 -> merge, parent = [1, 1, 3, 3, 5]
edge [2, 3]: roots 1 and 3 -> merge, parent = [1, 1, 1, 3, 5]
edge [4, 5]: roots 1 and 5 -> merge, parent = [1, 1, 1, 1, 1]
edge [1, 5]: roots 1 and 1 -> same group, redundant
The edge [2,3] merges two groups of two nodes: roots 1 and 3, with equal sizes, so 3 goes under 1. Node 4 still points to 3 at that moment. When the edge [4,5] looks for the root of 4, path halving makes 4 point straight to 1, and the final parent list is all 1s. The last edge finds both ends in the group of root 1, so it is the answer.
Complexity
Time: O(n · α(n)), nearly O(n). Each of the n edges costs two calls to find and a constant amount of other work, and with union by size and path halving each find costs O(α(n)) amortized.
Space: O(n) for the parent and size arrays.
Edge cases and common mistakes
- The smallest graph. A triangle,
[[1,2],[1,3],[2,3]], gives[2, 3]. Any of its edges could be removed, and the last one is returned. - The answer isn't always the last edge. In
[[1,2],[2,3],[3,4],[1,4],[1,5]], returning the last edge would give[1, 5], which is not on the cycle. The answer is[1, 4]. In[[1,4],[3,4],[1,3],[1,2],[4,5]]the last edge is[4, 5], and the answer is[1, 3]. - Edges joining separate groups. In
[[1,2],[3,4],[2,3],[4,5],[1,5]], the edge[2,3]connects two groups that already exist, and it is not redundant. Only[1,5]finds both ends already joined. - Other results.
[[1,2],[1,3],[3,4],[2,4]]gives[2, 4],[[1,2],[2,3],[1,3]]gives[1, 3], and[[1,2],[1,3],[1,4],[3,4]]gives[3, 4]. - A long chain. For 1000 nodes joined in a line, with the last edge
[1, 1000]closing the loop, the method returns[1, 1000]. - Index 0. Nodes start at 1, so the arrays have
n + 1entries. - Comparing the nodes instead of the roots. Two nodes can be in the same group without being equal, and without being direct neighbours. Only the roots tell whether the groups match.
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].[[1,2],[1,3],[1,4],[3,4]]gives[3, 4].
