A tree with n nodes labelled 1 to n had exactly one extra edge added, so the graph now contains one cycle. You are given the edges in edges as pairs [a, b]. Return an edge whose removal turns the graph back into a tree. If several edges qualify, return the one that appears last in the input.
[2,3], the last edge of the cycle, leaves a tree.- n == edges.length
- 3 <= n <= 1000
- 1 <= a < b <= n (or any order)
- No repeated edges, the graph is connected
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force removes each edge in turn (from the last) and checks with a DFS whether the rest is still a connected tree, which is O(n^2). Better: build the graph edge by edge. While the graph is still a forest, every new edge either joins two different components or connects two nodes that are already in the same component. The second case is exactly the edge that creates the cycle, and since we scan in input order it is also the last cycle edge in the input. Union Find answers "same component?" in near constant time with path compression and union by rank.
Algorithm
- Create a parent array where every node is its own root.
- For each edge
[a, b]in order, find the roots ofaandb. - If the roots are equal,
aandbare already connected: return this edge. - Otherwise union the two roots (attach the smaller rank under the bigger one).
O(n * α(n)), practically O(n)Space: O(n)class Solution: def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: n = len(edges) parent = list(range(n + 1)) rank = [0] * (n + 1) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # path halving x = parent[x] return x for a, b in edges: ra, rb = find(a), find(b) if ra == rb: return [a, b] # a and b were already connected if rank[ra] < rank[rb]: ra, rb = rb, ra parent[rb] = ra if rank[ra] == rank[rb]: rank[ra] += 1 return []