Problem overview
A tree is a connected graph with no cycle. You start with a tree of n nodes numbered 1 to n and add one extra edge between two nodes that weren't directly joined. The function findRedundantConnection receives the resulting edges, a [][]int of length n where each element is a pair of nodes. It returns an edge that can be removed so the remaining n - 1 edges form a tree again. If several edges would work, it returns the one that comes last in edges.
With edges = [[1 2] [1 3] [2 3]] the three edges form the cycle 1, 2, 3, and removing any one leaves a tree. The last of them is [2 3]. With [[1 2] [2 3] [3 4] [1 4] [1 5]] the cycle is 1, 2, 3, 4, and the answer is [1 4]: the edge [1 5] comes later in the input, but removing it would cut node 5 off. With [[1 2] [3 4] [2 3] [4 5] [1 5]] all five edges form one cycle, and the answer is [1 5].
The statement asks for about O(n·α(n)) time, where α is the inverse Ackermann function, which stays below 5 for any input a computer can hold, and O(n) extra space.
Approach: union-find, edge by edge
A slow idea tries the edges from the last one back, removes each and checks with a depth-first search whether the rest is still a connected tree. That costs O(n²).
The faster idea adds the edges one at a time, in the given order, and keeps track of which nodes are connected with union-find. Each group of connected nodes is stored as a small tree: every node points to a parent, and the root, which is its own parent, names the group. An edge whose two ends already have the same root closes a cycle.
The graph has exactly one cycle. Every edge on it can be removed, and an edge that is not on it cannot, because removing it would cut the tree in two. The cycle closes when its last edge arrives, because all of its other edges came before. So the first edge that joins two nodes already in the same group is the answer.
Tracing the third example
Running the algorithm on [[1 2] [3 4] [2 3] [4 5] [1 5]] and printing the roots of both ends before each merge gives:
[1 2] roots 1 2
[3 4] roots 3 4
[2 3] roots 1 3
[4 5] roots 1 5
[1 5] roots 1 1The edge [2 3] joins the groups of 1 and 3, which are different, so it merges them. For [1 5] both roots are 1: the nodes are already connected, so this edge closes the cycle and is returned.
Step by step
- Store
len(edges)inn. A tree ofnnodes hasn - 1edges, plus the extra one givesn, so it is also the number of nodes. - Create
parentwithmake,n + 1ints. Nodes start at 1, so nodeisits at indexiand index 0 is never used. - Create
sizethe same way.size[r]counts the nodes in the group whose root isr. - Initialise every node in a loop from 0 to
n: setparent[i] = i, so each node is the root of a group of one, andsize[i] = 1, sincemakefilled the sizes with zeros. - Go over
edgesin order withrange. - Find both roots:
rootAforedge[0]androotBforedge[1], with the helperfind. - Detect the cycle. If
rootA == rootB, the two ends are already connected, so returnedge. - Union by size. If
size[rootA] < size[rootB], swap them withrootA, rootB = rootB, rootA, sorootAis the root of the larger group. - Merge:
parent[rootB] = rootAhangs the smaller tree under the larger one. - Update the size:
size[rootA] += size[rootB]. - Return
[]int{}after the loop. Since the input always has an extra edge, the loop returns first, and this line is only there because the function must return a value on every path. - Write
find. Whileparent[x] != x, setparent[x] = parent[parent[x]]and thenx = parent[x], and returnxat the end. This is path halving.
The solution in Go
func findRedundantConnection(edges [][]int) []int {
n := len(edges)
parent := make([]int, n + 1)
size := make([]int, n + 1)
for i := 0; i <= n; i++ {
parent[i] = i
size[i] = 1
}
for _, edge := range edges {
rootA := find(parent, edge[0])
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 []int{}
}
func find(parent []int, x int) int {
for parent[x] != x {
parent[x] = parent[parent[x]]
x = parent[x]
}
return x
}The Go details worth a closer look:
- Slices are shared.
findreceives the slice header by value, but it points at the same array, so the writes toparentinsidefindare seen byfindRedundantConnection. Reassigningx, on the other hand, changes onlyfind's own copy of the number. - A
forwith only a condition. Go has nowhile.for parent[x] != xwalks up to the root with no recursion, however long the chain is. - Swapping in one line.
rootA, rootB = rootB, rootAevaluates the right side first and then assigns both, so no temporary variable is needed. - The returned edge.
return edgereturns the same two-element slice that was in the input, not a copy. - Path halving and union by size. Halving makes each node on the walk skip a level, so later walks are shorter. Union by size keeps trees shallow because a node only moves one level deeper when its group at least doubles. Together they give the
O(α(n))amortized cost per call.
Complexity
Time: O(n·α(n)), nearly O(n). Each of the n edges costs two calls to find, each O(α(n)) amortized, plus constant work for the merge.
Space: O(n) for the parent and size slices.
Edge cases and common mistakes
- Returning the last edge of the input. That is wrong whenever the last edge isn't on the cycle. For
[[1 2] [2 3] [3 4] [1 4] [1 5]]it would give[1 5], but the answer is[1 4]. - The extra edge comes early. For
[[1 2] [2 3] [1 3] [3 4] [4 5]]the function returns[1 3], even though two more edges follow it. - A cycle through a hub. For
[[1 2] [1 3] [1 4] [2 4]]the answer is[2 4], and for[[1 2] [1 3] [1 4] [1 5] [4 5]]it is[4 5]. - The longest cycle. A chain from 1 to 1000 followed by
[1 1000]returns[1 1000]. The search stays fast and never recurses. - Slices of size
n. Node numbers go up ton, soparentneedsn + 1entries. Withnentries and the first example, the program stops withindex out of range [3] with length 3. - Comparing the nodes, not the roots. Two nodes are connected exactly when
findgives them the same root. Comparingedge[0]withedge[1]directly never detects a cycle.
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] [4 5]]gives[1 3].[[1 2] [1 3] [1 4] [2 4]]gives[2 4].
