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 != viRedundant Connection II asks you to identify an edge that should be removed so that a directed graph becomes a valid rooted tree. The challenge comes from two possible issues: a node having two parents, or the presence of a cycle. A common strategy combines parent tracking with the Union-Find (Disjoint Set) data structure.
First, scan edges to detect whether any node has two incoming edges. If such a case appears, temporarily record the conflicting edges. Then use Union-Find to process edges and check whether adding an edge forms a cycle. Depending on whether a cycle appears and whether a node had two parents, you can determine which edge must be removed.
This approach efficiently separates the two failure cases (cycle vs. double parent) and resolves them with near-constant-time union operations. The algorithm runs in approximately O(n * α(n)) time using Union-Find, where α is the inverse Ackermann function, with O(n) space for parent and rank structures.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Union-Find with parent tracking | O(n * α(n)) | O(n) |
| Graph traversal validation (DFS/BFS) | O(n) | O(n) |
NeetCode
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.
Time Complexity: O(n), where n is the number of edges.
Space Complexity: O(n), for storing the parent and rank arrays.
1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct UnionFind {
5 int* parent;
6 int
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.
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.
Time Complexity: O(n^2) with recursive verification.
Space Complexity: O(n), memoizing visited nodes.
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
The problem is challenging because it combines two separate graph issues: cycle detection and nodes with two parents. Handling both cases correctly requires careful logic and often a hybrid strategy involving Union-Find and parent tracking.
Yes, variations of cycle detection and Union-Find problems frequently appear in FAANG-style interviews. Redundant Connection II is particularly valuable because it tests understanding of directed graphs, disjoint sets, and edge-case reasoning.
The optimal approach uses Union-Find combined with parent tracking. First detect if any node has two parents, then run Union-Find to identify cycles. By analyzing these two conditions, you can determine which edge must be removed.
The Union-Find (Disjoint Set Union) data structure is the most effective for detecting cycles efficiently. It supports near constant-time union and find operations, making it ideal for incremental edge processing in graph problems.
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.