0% completed
Problem Statement
Given an undirected graph containing 1
to n
nodes. The graph is represented by a 2D array of edges
, where edges[i] = [a<sub>i</sub>, b<sub>i</sub>], represents an edge between a<sub>i</sub>, and b<sub>i</sub>.
Identify one edge that, if removed, will turn the graph into a tree.
A tree is a graph that is connected and has no cycles.
Assume that the graph is always reducible to a tree by removing just one edge.
If there are multiple answers, return the edge that occurs last in the input.
Examples
- Example 1:
- Input:
[[1,2], [1,3], [3,4], [1,4], [1,5]]
- Input:
- Expected Output:
[1,4]
- Justification: The edge
[1,4]
is redundant because removing it will eliminate the cycle1-3-4-1
while keeping the graph connected.
- Example 2:
- Input:
[[1,2], [2,3], [3,1], [3,4]]
- Input:
- Expected Output:
[3,1]
- Justification: The edge
[3,1]
creates a cycle1-2-3-1
. Removing it leaves a tree with no cycles.
- Example 3:
- Input:
[[1,2], [2,3], [3,4], [4,2], [5,6]]
- Input:
- Expected Output:
[4,2]
- Justification: The edge
[4,2]
adds a cycle2-3-4-2
in one part of the graph. Removing this edge breaks the cycle, and the remaining graph is a tree.
Constraints:
n == edges.length
3 <= n <= 1000
edges[i].length == 2
- 1 <= a<sub>i</sub> < b<sub>i</sub> <= edges.length
- a<sub>i</sub> != b<sub>i</sub>
- There are no repeated edges.
- The given graph is connected.
Solution
The solution to this problem employs the Union-Find algorithm, which is effective for cycle detection in graphs. Initially, each node is considered as a separate set. As we iterate through the edges of the graph, we use the Union-Find approach to determine if the nodes connected by the current edge are already part of the same set. If they are, it indicates the presence of a cycle, and this edge is the redundant one. Otherwise, unite these two sets, meaning connect the nodes without forming a cycle. This approach focuses on progressively merging nodes into larger sets while keeping an eye out for the edge that connects nodes already in the same set.
Step-by-Step Algorithm
-
Initialization:
- Create a
parent
array of sizeedges.Length + 1
(to accommodate 1-based node indexing). - Initialize each element in the
parent
array to be its own parent.
- Create a
-
Process Each Edge:
- For each edge in the input
edges
array:- Extract the two nodes,
node1
andnode2
. - Use the
find
operation to determine the root ofnode1
. - Use the
find
operation to determine the root ofnode2
. - If both nodes have the same root, a cycle is detected, and the current edge is redundant. Return this edge.
- Otherwise, use the
union
operation to merge the sets containingnode1
andnode2
.
- Extract the two nodes,
- For each edge in the input
-
Return the Result:
- If no redundant connection is found (which should not happen as per the problem statement), return an empty array.
Algorithm Walkthrough
Consider the input [[1,2], [1,3], [3,4], [1,4], [1,5]].
- Initialize the parent array where
parent[i] = i
.
- Consider the edge
[1,2]
:- Find the parents of
1
and2
. Since they're different, union them by making one the parent of the other.
- Find the parents of
- Next, consider the edge
[1,3]
:- Their parents are different, so union them.
- Now, consider the edge
[3,4]
:- Again, different parents, so union them.
- Consider the edge
[1,4]
:- Find operations for both nodes return the same parent, indicating a cycle. We identify
[1,4]
as the redundant edge.
- Find operations for both nodes return the same parent, indicating a cycle. We identify
Code
Complexity Analysis:
Time Complexity
-
Initialization:
- Initializing the
parent
array takes O(N) time, where (N) is the number of nodes.
- Initializing the
-
Find Operation:
- The
find
operation with path compression has an amortized time complexity of O(logN), which is almost equal to O(\alpha(N)), where \alpha(N) is the inverse Ackermann function, which is very close to constant.
- The
-
Union Operation:
- The
union
operation involves twofind
operations and one assignment, leading to a time complexity of O(\alpha(N)) per union.
- The
-
Processing Edges:
- For each edge, we perform two
find
operations and oneunion
operation. Since there are (E) edges, the total time complexity for processing all edges is O(N \alpha(N)), where N is a number of edges.
- For each edge, we perform two
The total time complexity is O(N + N \alpha(N)), which is equal to O(N \alpha(N)).
Space Complexity
- The
parent
array requires O(N) space to store the parent of each node.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible