Redundant Connection
Medium · Graphs · Graph · Union Find · Depth-First Search · Breadth-First Search
Problem
A tree on n nodes labelled 1 to n had one extra edge added between two different nodes, and that edge was not already present. The result is a connected undirected graph with exactly one cycle.
The graph is given as an array edges of length n, where edges[i] = [a, b] is an edge between a and b.
Return an edge whose removal turns the graph back into a tree of n nodes. If several edges would work, return the one that appears last in edges.
Examples
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] Output: [1,4]
The cycle is 1-2-3-4-1; among its edges, [1,4] is listed last.
Input: edges = [[2,3],[1,2],[1,3]] Output: [1,3]
All three edges are on the cycle, so the last one, [1,3], is returned.
Input: edges = [[1,2],[2,3],[1,3],[3,4]] Output: [1,3]
The cycle 1-2-3 is closed by [1,3]; the later edge [3,4] is not on it.
Constraints
- n == len(edges)
- 3 <= n <= 1000
- len(edges[i]) == 2
- 1 <= a < b <= n
- There are no repeated edges
- The graph is connected
Approaches
- Baseline: search before adding each edge — time O(n²), space O(n)
Follow-up
If the edges were directed (a rooted tree plus one extra edge), the extra edge could also give a node two parents, which the first use case handles. The second use case keeps the union-find but asks when a growing set of edges first connects everyone.
Related problems
Start free on Cariara · Coding problems · System design studio
