Problem overview
A tree is an undirected graph that is connected and has no cycle, so there is exactly one path between any two nodes. The method findRedundantConnection receives edges, the edges of a tree of n nodes (numbered 1 to n) plus one extra edge. That makes n edges in total, and the graph has exactly one cycle. The method 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], [1, 3], [2, 3]] the three edges form the cycle 1 - 2 - 3 - 1. Removing any one of them leaves a tree, and [2, 3] comes last, so the answer is [2, 3]. 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 it is not on the cycle: removing it would cut node 5 off. Of the four edges on the cycle, [1, 4] is the last, so the answer is [1, 4].
Approach: add the edges in order and watch for a cycle
Trying the edges from the last one back, removing each and checking with a depth-first search whether the rest is still connected, costs O(n^2). Union-find does better.
Union-find keeps the nodes in groups of connected nodes. Each group is a tree in which every node points to a parent, and the root, the one node that is its own parent, names the group. Two operations are needed: find walks up from a node to the root of its group, and a union hangs one group's root under the other's.
Add the edges one by one, in the order they are given. For an edge between a and b, find the roots of both. If the roots differ, the edge joins two groups, so merge them. If the roots are equal, a and b are already connected through earlier edges, and this edge closes a cycle. Because the graph has exactly one cycle, and all the other edges of that cycle came before this one, this is the edge of the cycle that comes last, and it is the answer. Edges that come after it, like [1, 5] in the second example, are never looked at.
Two refinements keep the trees shallow. Union by size always hangs the smaller group under the larger one, so a node moves one level deeper only when its group at least doubles, and no path to a root gets longer than log2(n) steps. Path halving makes each node visited by find point to its grandparent, so later walks are shorter. Together they make each operation O(α(n)) amortized, where α is the inverse Ackermann function, below 5 for any input a computer can hold.
Here is the second example, edge by edge. The tables show parent and size after each merge, with index 0 unused:
| Edge | parent | size |
|---|---|---|
[1, 2] | [0, 1, 1, 3, 4, 5] | [1, 2, 1, 1, 1, 1] |
[2, 3] | [0, 1, 1, 1, 4, 5] | [1, 3, 1, 1, 1, 1] |
[3, 4] | [0, 1, 1, 1, 1, 5] | [1, 4, 1, 1, 1, 1] |
[1, 4] | both roots are 1: this edge closes the cycle and is returned | |
Step by step
- Count the edges. Store
edges.countin the constantn. A tree ofnnodes hasn - 1edges, and with the extra one there aren, so this is also the number of nodes. - Create
parentasArray(0...n), so thatparent[i]isiand every node starts alone. The closed range includesn, and the array hasn + 1entries because the nodes are numbered from 1 and index 0 stays unused. It is avar, becausefindchanges it. - Create
size,n + 1ones.size[r]counts the nodes of the group whose root isr; only the roots' entries are kept up to date. - Loop over
edgesin the given order. The order decides which edge of the cycle is returned. - Find the first root:
var rootA = find(&parent, edge[0]). It is avarbecause the union may swap it. - Find the second root the same way, in
rootB. - Detect the cycle. If
rootA == rootB, returnedge. - Pick the larger group. If
size[rootA] < size[rootB], swap the two roots with one tuple assignment,(rootA, rootB) = (rootB, rootA). - Merge by setting
parent[rootB] = rootA. - Update the size with
size[rootA] += size[rootB].rootBis not a root any more, so its entry is never read again. - Return
[]after the loop. The input always has an extra edge, so the loop returns before it ends, but the method must return a value on every path. - Write
findwith aninoutarrayparentand anode, returning anInt. - Copy
nodeinto avar x. Parameters are constants, andxwalks up the tree. - Loop while
parent[x] != x, that is, whilexis not a root. - Halve the path: set
parent[x] = parent[parent[x]]. - Move up: set
x = parent[x], the grandparent, so each turn climbs two levels. - Return
x: the loop ends exactly at the root.
The solution in Swift
class Solution {
func findRedundantConnection(_ edges: [[Int]]) -> [Int] {
let n = edges.count
var parent = Array(0...n)
var size = [Int](repeating: 1, count: n + 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] {
(rootA, rootB) = (rootB, rootA)
}
parent[rootB] = rootA
size[rootA] += size[rootB]
}
return []
}
func find(_ parent: inout [Int], _ node: Int) -> Int {
var x = node
while parent[x] != x {
parent[x] = parent[parent[x]]
x = parent[x]
}
return x
}
}
The Swift details worth a closer look:
Array(0...n). A closed range0...nis a sequence of the integers from 0 tonincluded, andArray(...)turns it into[0, 1, ..., n]. With the half-open0..<nthe array would be one entry short, and the largest node would index out of bounds.inoutand&parent. Arrays are values and are copied when passed. Becausefindchangesparent(path halving) and those changes must last, it takes the array asinout, and the caller passes it with&.- Tuple swap.
(rootA, rootB) = (rootB, rootA)builds a pair from the right side and unpacks it into the left side, so no temporary variable is needed. return edge.edgeis the inner[Int]of the input, so the method returns the original pair, such as[2, 3].- Iteration, not recursion.
finduses awhileloop, so a long chain can't overflow the call stack.
Complexity
Time: O(n · α(n)), nearly O(n). The loop runs at most n times, each with two calls to find that cost O(α(n)) amortized with union by size and path halving, plus constant work for the merge.
Space: O(n): the arrays parent and size have n + 1 entries each.
Edge cases and common mistakes
- Returning the last edge of the input. The extra edge is not necessarily the last one. On the second example the last edge is
[1, 5], which is not on the cycle, and the answer is[1, 4]. - The cycle closes early in the list. For
[[1, 2], [2, 3], [1, 3], [3, 4]]the method returns[1, 3], and for[[1, 2], [1, 3], [1, 4], [3, 4], [1, 5]]it returns[3, 4]. Later edges don't matter. - A cycle closed by two separate groups. In
[[1, 2], [3, 4], [2, 3], [4, 5], [1, 5]], the edge[2, 3]joins the groups {1, 2} and {3, 4}: both nodes were seen before, but the roots differ, so it is a merge and not a cycle. The cycle closes at[1, 5], and that is the answer. After the fourth edge, the nodes 1 to 5 are all in one group:
| Edge | parent | size |
|---|---|---|
[1, 2] | [0, 1, 1, 3, 4, 5] | [1, 2, 1, 1, 1, 1] |
[3, 4] | [0, 1, 1, 3, 3, 5] | [1, 2, 1, 2, 1, 1] |
[2, 3] | [0, 1, 1, 1, 3, 5] | [1, 4, 1, 2, 1, 1] |
[4, 5] | [0, 1, 1, 1, 1, 1] | [1, 5, 1, 2, 1, 1] |
[1, 5] | both roots are 1: cycle, returned | |
- Index 0. The arrays have
n + 1entries because nodes start at 1. Sizing them withnmakes the last node index out of bounds. - Path halving in action. With
parent = [0, 1, 1, 2, 3, 4], a chain 5 - 4 - 3 - 2 - 1, the callfind(&parent, 5)returns 1 and leavesparentas[0, 1, 1, 1, 3, 3]: nodes 5 and 3 now point two levels higher.
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], [1, 5]]gives[3, 4].
