Watch 10 video solutions for Redundant Connection II, a hard level problem involving Depth-First Search, Breadth-First Search, Union Find. This walkthrough by Hua Hua has 11,102 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.
The given input is a directed graph that started as a rooted tree with n nodes (with distinct values from 1 to n), with one additional directed edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [ui, vi] that represents a directed edge connecting nodes ui and vi, where ui is a parent of child vi.
Return an edge that can be removed so that the resulting graph is a rooted tree of n nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.
Example 1:
Input: edges = [[1,2],[1,3],[2,3]] Output: [2,3]
Example 2:
Input: edges = [[1,2],[2,3],[3,4],[4,1],[1,5]] Output: [4,1]
Constraints:
n == edges.length3 <= n <= 1000edges[i].length == 21 <= ui, vi <= nui != viProblem Overview: You are given a directed graph that was originally a rooted tree with n nodes, but one extra edge was added. That extra edge creates either a node with two parents, a cycle, or both. The task is to identify and return the redundant edge that should be removed so the graph becomes a valid rooted tree again.
Approach 1: Union-Find with Parent Check (O(n) time, O(n) space)
This approach combines Union Find with an explicit parent tracking step. While iterating through edges, you first check if a node already has a parent. If it does, you record two candidate edges: the earlier parent edge and the later conflicting one. After that, run union-find to detect cycles while skipping the second candidate edge temporarily. If a cycle still forms, the earlier edge is the redundant one; otherwise the later edge is the answer. Union-Find operations like find and union with path compression keep the total complexity near linear, roughly O(n α(n)). This method directly handles the two tricky scenarios: nodes with two parents and pure cycles.
Approach 2: Graph Traversal & Cycle Detection (O(n) time, O(n) space)
This method treats the graph as a directed structure and uses traversal techniques from Depth-First Search or Breadth-First Search. First, track incoming edges to detect if any node receives two parents. If such a node exists, temporarily remove one candidate edge and run cycle detection using DFS. The traversal checks whether a back-edge appears, which indicates a cycle in the graph. If removing the later edge resolves the cycle, it is redundant; otherwise the earlier edge must be removed. This approach mirrors how you would manually validate a directed tree: ensure every node except the root has exactly one parent and verify there are no cycles.
Recommended for interviews: The Union-Find with parent check approach is the expected solution. It cleanly handles both constraints of the problem—detecting a node with two parents and identifying cycles—while keeping the complexity near linear. Explaining the three possible cases (two parents, cycle, or both) shows strong graph reasoning. A traversal-based solution demonstrates understanding of cycle detection, but Union-Find typically leads to simpler and more reliable implementation under interview pressure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find with Parent Check | O(n α(n)) ~ O(n) | O(n) | Best general solution. Handles both two-parent conflict and cycle detection efficiently. |
| Graph Traversal & Cycle Detection | O(n) | O(n) | Useful when reasoning about directed graphs using DFS/BFS or when Union-Find is not preferred. |