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 != viThis 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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. |
Redundant Connection - Union Find - Leetcode 684 - Python • NeetCode • 123,096 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