In this problem, a tree is an undirected graph that is connected and has no cycles.
You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.
Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.
Example 1:
Input: edges = [[1,2],[1,3],[2,3]] Output: [2,3]
Example 2:
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] Output: [1,4]
Constraints:
n == edges.length3 <= n <= 1000edges[i].length == 21 <= ai < bi <= edges.lengthai != biProblem Overview: You receive a list of edges representing an undirected graph that started as a tree with n nodes. One additional edge was added, creating exactly one cycle. Your task is to return the edge that introduces the cycle (the redundant connection).
Approach 1: Union-Find Algorithm (O(n α(n)) time, O(n) space)
The most efficient solution uses the Union-Find (Disjoint Set Union) data structure to track connected components. Iterate through each edge (u, v). If u and v already belong to the same set, adding this edge would connect two nodes that are already connected, which forms a cycle. That edge is the redundant one. Otherwise, union their sets using path compression and union by rank to keep operations nearly constant time. This approach processes each edge once and avoids explicitly traversing the graph.
Union-Find works well because a valid tree never connects two nodes already in the same component. The moment that happens, a cycle is detected. With path compression, the amortized complexity becomes almost linear (O(n α(n)), where α is the inverse Ackermann function).
Approach 2: Depth-First Search (DFS) (O(n²) time, O(n) space)
This approach builds the graph incrementally using an adjacency list and checks connectivity before adding each edge. For every new edge (u, v), run a DFS from u to see if v is already reachable. If a path already exists, adding the edge would close a cycle, so that edge is redundant. If not, add the edge to the graph and continue.
The traversal uses Depth-First Search on the evolving graph. Each DFS may visit up to O(n) nodes, and you potentially run it for every edge, which leads to O(n²) time in the worst case. This solution is easier to reason about if you're thinking in terms of connectivity checks rather than disjoint sets.
Recommended for interviews: The Union-Find solution is what most interviewers expect. It demonstrates understanding of cycle detection in undirected graphs and familiarity with disjoint-set optimizations like path compression. The DFS approach shows solid graph fundamentals, but Union-Find is both cleaner and more efficient for this specific problem.
This approach utilizes the Union-Find (or Disjoint Set Union, DSU) data structure to detect cycles. The key operations in Union-Find are 'find', which determines the representative of a set, and 'union', which merges two sets. When processing each edge, we attempt to unite the vertices. If both vertices are already in the same set, a cycle is detected, and this edge is the redundant one.
This solution implements a Union-Find class with path compression and rank optimization to efficiently find and union nodes. By iteratively applying union operation on each edge, it detects the first edge causing a cycle, which is the redundant edge to be returned.
Time Complexity: O(n) where n is the number of edges because we process each edge once.
Space Complexity: O(n) due to the storage of the parent and rank arrays.
The DFS approach involves simulating the construction of the graph and utilizing DFS to detect cycles whenever a new edge is being added. If a cycle is detected upon adjacent traversal, that edge is the redundant one.
This solution constructs the graph incrementally while running DFS to check for paths from vertex u to vertex v before adding each edge. If the path exists, addition of the edge creates a cycle, thereby identifying it as redundant.
Time Complexity: O(n^2), potentially examining each pair of nodes connected by added edges in the worst case.
Space Complexity: O(n), dictated by recursive stack depth in the DFS and the graph representation.
According to the problem description, we need to find an edge that can be removed so that the remaining part is a tree with n nodes. We can traverse each edge and determine whether the two nodes of this edge are in the same connected component. If they are in the same connected component, it means this edge is redundant and can be removed, so we directly return this edge. Otherwise, we merge the two nodes connected by this edge into the same connected component.
The time complexity is O(n log n), and the space complexity is O(n). Here, n is the number of edges.
Python
Java
C++
Go
TypeScript
JavaScript
Here is a template approach using Union-Find for your reference.
The time complexity is O(n \alpha(n)), and the space complexity is O(n). Here, n is the number of edges, and \alpha(n) is the inverse Ackermann function, which can be considered a very small constant.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Union-Find Algorithm | Time Complexity: O(n) where n is the number of edges because we process each edge once. |
| Approach 2: Depth-First Search (DFS) | Time Complexity: O(n^2), potentially examining each pair of nodes connected by added edges in the worst case. |
| Union-Find | — |
| Union-Find (Template Approach) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find (Disjoint Set) | O(n α(n)) | O(n) | Best general solution for cycle detection while processing edges |
| Depth-First Search (DFS) | O(n²) | O(n) | Useful when practicing graph traversal or when Union-Find is unavailable |
Redundant Connection - Union Find - Leetcode 684 - Python • NeetCode • 131,453 views views
Watch 9 more video solutions →Practice Redundant Connection with our built-in code editor and test cases.
Practice on FleetCode