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.
This approach uses a Union-Find (Disjoint Set Union, DSU) structure to detect cycles and check for nodes with two parents. The goal is to handle two situations: a node having two parents, and a cycle existing in the graph. We iterate through the edges to identify a node with two parents and mark the offending edge. Then, we use the Union-Find structure to track cycles and find the redundant connection based on the identified edges.
The implementation uses a Union-Find data structure to manage connectivity among nodes and track potential redundant connections by checking parent-child relationships and detecting cycles. First, it checks whether any node has two parents. If found, it temporarily removes that edge and continues to apply Union-Find to check for any cycles. If a cycle exists without finding a node with two parents, the wrong edge is part of the cycle. Otherwise, it'll be the edge removed previously.
Time Complexity: O(n), where n is the number of edges.
Space Complexity: O(n), for storing the parent and rank arrays.
In this method, we focus on identifying two scenarios: an edge creating a cycle in the graph and a node with two parents. With graph traversal, primarily cross-check with parent pointers and DFS for cycle confirmation, fine-tuning insights to pinpoint a last array occurrence redundant connection.
Utilizing DFS, this C code ensures settings target node connections and traces for potential overlapping cycles, using indications to determine redundancy. Understanding traversal in view of directed graph properties is fundamental to isolating missteps.
Time Complexity: O(n^2) with recursive verification.
Space Complexity: O(n), memoizing visited nodes.
| Approach | Complexity |
|---|---|
| Union-Find with Parent Check | Time Complexity: O(n), where n is the number of edges. Space Complexity: O(n), for storing the parent and rank arrays. |
| Graph Traversal & Cycle Detection | Time Complexity: O(n^2) with recursive verification. Space Complexity: O(n), memoizing visited nodes. |
| 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. |
Huahua LeetCode 685. Redundant Connection II - Job Hunting EP83 • Hua Hua • 11,102 views views
Watch 9 more video solutions →Practice Redundant Connection II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor