Problem overview
A tree is a connected 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 directly joined. The function findRedundantConnection receives the resulting edges, a list of n pairs [a, b], and returns an edge whose removal leaves a tree again. When several edges would work, it returns the one that comes last in the list.
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 that's the answer. For [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] the cycle is 1 - 2 - 3 - 4 - 1 and the answer is [1, 4]. The edge [1, 5] comes later in the list, but removing it would cut node 5 off.
Approach: add edges one by one and detect the first cycle
One way is to try each edge from the last one back, remove it, and check with a depth-first search whether the rest is still connected. Each check costs O(n), so the total is O(n^2).
A better idea is to add the edges in the given order and ask, before each one, whether its two nodes are already connected. If they are, this edge closes a cycle. The graph has exactly one cycle, and removing any edge of the cycle leaves a tree, while removing an edge that isn't on it splits the tree in two. The cycle closes when the last of its edges arrives, because all its other edges came earlier. So the first edge whose ends are already connected is the last edge of the cycle, which is the answer.
The question "are these two nodes connected so far?" is what union-find answers. Each group of connected nodes is stored as a tree: every node points to a parent, and the root, which is its own parent, names the group. Two nodes are in the same group exactly when they lead to the same root. Merging two groups hangs one root under the other. Two refinements keep the trees shallow: union by size (the smaller tree goes under the larger one) and path halving (while climbing, each node skips to its grandparent). Together they make each operation cost O(α(n)) amortized, where α is the inverse Ackermann function, which stays below 5 for any input a computer can hold.
Here is the run on [[1, 2], [3, 4], [2, 3], [4, 5], [1, 5]]. After each merge, the table shows the parent list (index 0 is unused):
start parent [0, 1, 2, 3, 4, 5]
[1, 2] roots 1 2 -> parent [0, 1, 1, 3, 4, 5]
[3, 4] roots 3 4 -> parent [0, 1, 1, 3, 3, 5]
[2, 3] roots 1 3 -> parent [0, 1, 1, 1, 3, 5]
[4, 5] roots 1 5 -> parent [0, 1, 1, 1, 1, 1]
[1, 5] roots 1 1 -> same group: cycle, return [1, 5]The edge [2, 3] joins the groups {1, 2} and {3, 4}, which are different, so it merges them. When [1, 5] arrives, 1 and 5 already share the root 1, so that edge closes the cycle 1 - 2 - 3 - 4 - 5 - 1.
Step by step
- Store the edge count in
n. A tree ofnnodes hasn - 1edges, and the extra edge makes itn, so the count is also the number of nodes. - Create
parentwithlist(range(n + 1)). Nodes start at 1, so the list hasn + 1entries, index 0 is unused, and every node starts as the root of its own group. - Create
sizeasn + 1ones. For a rootr,size[r]counts the nodes in its group. 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
rootAforedge[0]with the helperself.find, written at the end. - Find
rootBforedge[1]the same way. - Test for the cycle. If
rootA == rootB, the ends were already connected through earlier edges, so returnedge. - Make
rootAthe larger group. Ifsize[rootA] < size[rootB], swap the two names with one tuple assignment. This is union by size. - Merge. Set
parent[rootB] = rootA, hanging the smaller tree under the larger one's root. - Update the size with
size[rootA] += size[rootB]. - Return
[]after the loop. The input always has an extra edge, so the loop returns first, but the function must return a value on every path. - Write
findas a method takingparentand a nodex. - Climb while
parent[x] != x. The root is the only node that is its own parent. A loop has no call-stack limit, however long the climb. - Halve the path. Set
parent[x]toparent[parent[x]], so the node skips a level for later walks. - Move up by setting
x = parent[x], which is now the old grandparent. - Return
x, the root.
The solution in Python
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
n = len(edges)
parent = list(range(n + 1))
size = [1] * (n + 1)
for edge in edges:
rootA = self.find(parent, edge[0])
rootB = self.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 []
def find(self, parent: List[int], x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
The Python details worth a closer look:
- Swapping with a tuple.
rootA, rootB = rootB, rootAevaluates the right side first, so the two names exchange values without a temporary variable. - The list is shared.
findreceivesparentas the same list object, so its assignments toparent[x]are visible to the caller. That is how path halving persists between calls. - The returned edge is the input's own list.
return edgegives back the very list that sits inedges, not a copy. The call on[[1, 2], [1, 3], [2, 3]]returns an object thatisthe third element of the input. - An iterative
find. Python's default recursion limit is 1000. The loop doesn't depend on it, which keepsfindsafe on any shape of tree.
Complexity
Time: O(n · α(n)), nearly O(n). Each of the n edges makes two calls to find, each O(α(n)) amortized thanks to union by size and path halving, plus constant work to merge.
Space: O(n). parent and size have n + 1 entries each.
Edge cases and common mistakes
- The smallest input.
[[1, 2], [2, 3], [1, 3]]returns[1, 3], the last edge of the triangle. - An edge after the cycle. For
[[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]the function returns[1, 4], not the last edge of the input, which is[1, 5]. Removing[1, 5]would disconnect node 5. - A star plus one edge.
[[1, 2], [1, 3], [1, 4], [3, 4]]returns[3, 4]. - A node seen before. In the example traced above,
[2, 3]doesn't close a cycle even though both nodes have already appeared, because they were in separate groups. Checking whether the nodes have been seen is not enough; the roots must be compared. - Comparing parents instead of roots.
parent[a] == parent[b]is not the same test: a node can sit several levels below its root. - Allocating
nentries. Nodes are numbered from 1, so lists of lengthnmake nodenan out-of-range index. - Skipping union by size and path halving. The answer stays correct, but the trees can grow into long chains and each
findinto anO(n)walk. On a chain of 1000 edges that ends by connecting 1 and 1000, a plain version that hangs the first root under the second and never shortens paths climbs 999 steps in total before it returns[1, 1000].
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]]gives[1, 3].[[1, 2], [1, 3], [1, 4], [3, 4]]gives[3, 4].
