The problem
A tree — a connected graph with no cycles — on nodes 1 to n had one extra edge added, so now it has n edges and exactly one cycle.
Return an edge whose removal leaves a tree. If several would, return the one that comes last in edges.
Examples
- Input
edges = [[1, 2], [1, 3], [2, 3]]
- Output
[2, 3]
- Input
edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
- Output
[1, 4]
Constraints
- 3 ≤ n ≤ 1000
edges.lengthis n- 1 ≤ a < b ≤ n, and no edge repeats.
- The graph is connected.
The idea
Add the edges one at a time, keeping track of which nodes are already connected. The first edge whose two ends are already connected closes the cycle — and since the cycle is completed by exactly that edge, it is the last edge of the cycle in the list, which is the one asked for.
Union-find tracks connected groups: each node points toward a representative of its group; find follows the pointers, union hangs one group’s representative under another’s. Hanging the smaller group under the larger, and shortening paths as they are followed, keeps every operation almost constant time.
- Time
- O(n · α(n)) — α grows so slowly it is below 5 for any real n
- Space
- O(n)
Solution · every language run against every case
class Solution: def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: # Union-find: each node points toward a representative of its connected group. parent = list(range(len(edges) + 1)) size = [1] * (len(edges) + 1) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # halve the path as we go x = parent[x] return x for a, b in edges: ra, rb = find(a), find(b) if ra == rb: return [a, b] # already connected: this edge closes a cycle if size[ra] < size[rb]: ra, rb = rb, ra parent[rb] = ra # hang the smaller group under the larger size[ra] += size[rb] return []