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 != biThe key idea in #684 Redundant Connection is to detect the edge that creates a cycle in an undirected graph. Since the graph initially forms a tree and then receives one extra edge, that additional edge will connect two nodes that are already indirectly connected.
A common and efficient strategy is using the Union-Find (Disjoint Set Union) data structure. As you iterate through each edge, check whether the two nodes already belong to the same set using find(). If they do, adding this edge would form a cycle, making it the redundant connection. Otherwise, merge their sets using union().
An alternative approach uses DFS or BFS. Before adding an edge, perform a traversal to see if a path already exists between the two nodes. If a path exists, the current edge creates a cycle.
The Union-Find method is generally preferred because it processes edges efficiently with near-constant time operations, making it well suited for graph connectivity problems.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Union-Find (Disjoint Set) | O(n α(n)) | O(n) |
| DFS / BFS Cycle Check | O(n^2) in worst case | O(n) |
NeetCode
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.
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.
1class UnionFind:
2 def __init__(self, size):
3 self.root = list(range(size))
4 self.rank = [1
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.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, graph connectivity and Union-Find problems like Redundant Connection are commonly discussed in technical interviews at top companies. They test understanding of cycles, graph traversal, and efficient data structure design.
Yes, you can use DFS or BFS to check if a path already exists between two nodes before adding an edge. If a path exists, the edge would create a cycle, making it redundant. However, this approach is usually less efficient than Union-Find.
The optimal approach uses the Union-Find (Disjoint Set Union) data structure. It helps track connected components efficiently and detects when an edge connects two nodes already in the same set, indicating a cycle.
Union-Find is the most suitable data structure for this problem because it efficiently manages connectivity and cycle detection in graphs. It supports near constant-time union and find operations with path compression and rank optimization.
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.