685. Redundant Connection II
Problem Description
The problem presents a scenario where we are given a directed graph that was originally a rooted tree with n
nodes, each uniquely identified with values from 1
to n
. However, one extra directed edge was added to this tree that created a graph which might no longer be a tree. A tree is a type of graph that has no cycles (no path from a node back to itself), and for a rooted tree, there is one specific node (the root) that has no parents, while all other nodes have exactly one parent.
Our goal is to find the added edge that, when removed, will return the graph to its previous state of being a rooted tree. The input to the problem is a 2D array edges
where each subarray represents a directed edge from one node to another. In case there are multiple edges that could be removed to achieve this, the edge that appears last in the edges
array should be returned as the solution.
Flowchart Walkthrough
First, let's analyze the algorithm using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: The problem explicitly involves working with a directed graph to identify redundant edges.
Is it a tree?
- No: The presence of a redundant connection suggests it's not a strictly adhering tree structure since a tree shouldn’t have cycles or multiple parents.
Is the problem related to directed acyclic graphs (DAGs)?
- Yes: Although the graph has a redundant connection making it cyclic, the underlying structure we want to achieve should be a DAG (i.e., a tree, which is a special kind of DAG).
Does the problem involve topological sorting?
- No: The task is not about ordering elements but about identifying and removing a specific type of connection to achieve a tree structure.
Is the problem related to shortest paths?
- No: The problem does not concern calculating distances/path lengths between vertices.
Does the problem involve connectivity?
- Yes: The core of the problem is about maintaining connectivity in the graph after removing a redundant edge.
Is the graph weighted?
- No: The problem does not mention any weights associated with the edges; the concern is purely structural.
From this analysis following the flowchart, the suitable algorithm for handling this problem where we are dealing with a non-tree structured graph that should ideally be a tree (thus implicating cycles and potential multiple connections to a node) is to use DFS. DFS can be effectively utilized to detect cycles in directed graphs, which is crucial for identifying the redundant connection in this context.
Intuition
To solve this problem, we can leverage the Union-Find data structure which helps in tracking connected components and detecting cycles in a graph.
Here is the intuition behind this solution:
- Start by initializing the Union-Find data structure.
- There are two scenarios that can cause a graph that was once a tree to no longer be a tree: it can either have multiple parents for a single node (which we term as a
conflict
), or it can have a cycle. - Iterate through each edge
(u,v)
inedges
. Track the potentialconflict
by checking if a nodev
has already been marked to have a parent; if so, we store the index of this edge. - In parallel, use the Union-Find to determine if adding an edge
(u,v)
forms a cycle. If so, record the index of the edge forming the cycle. - If there is no conflict (no node has multiple parents), then the issue is solely due to a cycle; we return the edge that caused the cycle (which will be the last one that failed the union operation).
- If there is a conflict but no cycle detected, the conflict edge is the one to be removed.
- If both a cycle and a conflict exist, we must return the last edge that created the cycle related to the node with two parents, which we can backtrack from the Union-Find data structure.
The key to this solution is understanding the structure of a tree and the conditions that make a graph a tree. Applying Union-Find cleverly can detach the unwanted edge, restoring the tree.
Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.
Solution Approach
The provided solution employs the Union-Find algorithm for both the detection of cycles and the finding of a vertex with more than one parent. Let's walk through the implementation considering the two different cases that need to be handled:
Union-Find Data Structure:
The Union-Find algorithm is central to this solution approach. It traditionally includes two operations:
find
: This method compresses the path and looks for the root of the set that contains the given element. It facilitates the check for whether two elements are in the same set or not.union
: This method joins two sets if they are not already in the same set. In the context of trees, it connects two subtrees.
The UnionFind
class encapsulates these operations and maintains an array self.p
that serves as the parent pointer array, with a separate method union
to merge sets and find
to get the representative member (root) of a set.
Handling Conflicts and Cycles:
The solution distinguishes between two types of issues that may arise due to the additional edge:
- Conflict: This happens when a node has two parents. In the code, it checks if
p[v]
is already marked with a different parent; if so, it records the index of the second parent edge. - Cycle: Detected using Union-Find. A cycle happens when the
union
operation fails becauseu
andv
are already in the same set (have the same root).
Walkthrough of Implementation Steps:
- Initialize an instance of
UnionFind
, a listp
to track the direct parents, and variablesconflict
andcycle
toNone
. - Iterate over the provided list of edges
(u, v)
.- Check if node
v
has more than one parent by testing ifp[v]
has been set to something other than itself. Record the index of the second edge asconflict
if this is the case. - Perform the
union
operation for each edge(u, v)
. If it returnsFalse
, setcycle
to the current index as it signifies that adding this edge creates a cycle.
- Check if node
- Now assess the recorded
conflict
andcycle
.- If no
conflict
is found, return the last edge that failed tounion
which is causing the cycle. (i.e.edges[cycle]
). - If a
conflict
exists but nocycle
is detected, theconflict
edge is the problematic one, so returnedges[conflict]
. - If both
conflict
andcycle
exist, the issue arises due to the edge that creates a cycle with one node being part of the conflicting parentage. Return the first instance of the conflicting edge[p[v], v]
.
- If no
By differentiating between the presence of a conflict and a cycle, the algorithm can pinpoint the exact edge that, when removed, restores the original tree structure. The use of Union-Find provides an efficient way to manage set membership and connectivity which is crucial in solving this problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small graph that was originally a tree. This graph consists of 4 nodes, and we'll define the edge array as follows:
edges = [[1,2], [1,3], [3,4], [4,2]]
The original tree consisted of the first 3 edges ([1,2], [1,3], [3,4]). The last edge ([4,2]) was added, which might have introduced a cycle or a conflict.
Step 0: Initialization
We start by initializing the Union-Find data structure and two boolean flags conflict
and cycle
to None
. Also, we create an array p
of size n+1
, where n
is the number of nodes, to keep track of the direct parents, initialized by range(n+1). In this case, n=4
so p=[0, 1, 2, 3, 4]
.
Step 1: Iterating Over Edges
We iterate through the edge list:
-
Edge [1,2]:
- We check for conflicts, and since
p[2]
equals 2, which is the node itself, there's no parent conflict. - We try to union(1, 2), which is successful.
- We check for conflicts, and since
-
Edge [1,3]:
- There is no conflict at
p[3]
because it’s equal to 3. - Union(1, 3) is successful.
- There is no conflict at
-
Edge [3,4]:
p[4]
is equal to 4, so there is no conflict.- Union(3, 4) is successful.
Up to this point, we have no conflicts, and we have successfully built the tree.
- Edge [4,2]:
- We now encounter a conflict because
p[2]
was already set by the first edge to 1, so we setconflict = 3
(the index of the current edge). - When we try to union(4, 2), it returns
False
since 2 is already connected to 1, indicating a cycle. So we setcycle = 3
.
- We now encounter a conflict because
Step 2: Assess Conflict and Cycle
We have detected both a conflict and a cycle. The conflict occurs at node 2, which has two parents (node 1 and node 4), and the cycle is formed by the edge [4,2], which is a backward link in this tree.
Step 3: Determine the Edge to Remove
Since both a conflict and a cycle were detected, and since, according to the problem, we prefer to remove the edge that occurs later in the array in case of such a scenario, we track back the cycle to the conflicting node with two parents. Thus we identify that the edge [4,2] is responsible for both, which means it is the edge we want to remove to restore the original tree structure.
Conclusion
Our algorithm would return [4,2]
as the answer. This is the edge that when removed, the graph will revert to the original tree. The example illustrates the application of the Union-Find structure to efficiently check for cycles and the maintenance of a simple array to check for conflicts.
Solution Implementation
1from typing import List
2
3class UnionFind:
4 def __init__(self, size: int):
5 self.parent = list(range(size))
6 self.component_count = size
7
8 def union(self, node1: int, node2: int) -> bool:
9 root1 = self.find(node1)
10 root2 = self.find(node2)
11 if root1 == root2:
12 return False
13
14 # Merge sets by updating the parent
15 self.parent[root1] = root2
16 self.component_count -= 1
17 return True
18
19 def find(self, node: int) -> int:
20 # Path compression by making each looked-up node directly point to the root
21 if self.parent[node] != node:
22 self.parent[node] = self.find(self.parent[node])
23 return self.parent[node]
24
25
26class Solution:
27 def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
28 # The number of vertices in the graph is equal to the number of edges
29 num_vertices = len(edges)
30 parents = list(range(num_vertices + 1))
31 union_find = UnionFind(num_vertices + 1)
32 conflict = None # The index of the first edge causing a 'having two parents' conflict
33 cycle = None # The index of the first edge causing a cycle
34
35 # Check each edge for conflicts or cycles
36 for index, (from_vertex, to_vertex) in enumerate(edges):
37 # If to_vertex already has a parent, it means we have found a conflict
38 if parents[to_vertex] != to_vertex:
39 conflict = index
40 else:
41 parents[to_vertex] = from_vertex
42 # If union returns False, it means adding this edge introduced a cycle
43 if not union_find.union(from_vertex, to_vertex):
44 cycle = index
45
46 # If there is no conflict, return the edge that caused the cycle
47 if conflict is None:
48 return edges[cycle]
49
50 redundant_edge_target = edges[conflict][1]
51 # If there's a cycle, it means we need to return the edge where the cycle's vertex was first introduced
52 if cycle is not None:
53 return [parents[redundant_edge_target], redundant_edge_target]
54 # Otherwise, the edge causing conflict is the redundant connection
55 return edges[conflict]
56
1class Solution {
2 public int[] findRedundantDirectedConnection(int[][] edges) {
3 int numEdges = edges.length;
4 int[] parents = new int[numEdges + 1];
5 // Initialize each node to be its own parent
6 for (int i = 0; i <= numEdges; ++i) {
7 parents[i] = i;
8 }
9 UnionFind unionFind = new UnionFind(numEdges + 1);
10 int conflictEdgeIndex = -1;
11 int cycleEdgeIndex = -1;
12 for (int i = 0; i < numEdges; ++i) {
13 int from = edges[i][0], to = edges[i][1];
14 // Check if the current edge creates a conflict (i.e., a node with two parents)
15 if (parents[to] != to) {
16 conflictEdgeIndex = i;
17 } else {
18 // Set the parent of the 'to' node
19 parents[to] = from;
20 // Try to union the two nodes; if they are already connected, there is a cycle
21 if (!unionFind.union(from, to)) {
22 cycleEdgeIndex = i;
23 }
24 }
25 }
26 if (conflictEdgeIndex == -1) {
27 // If there is no conflict, return the edge causing the cycle
28 return edges[cycleEdgeIndex];
29 }
30 int to = edges[conflictEdgeIndex][1];
31 if (cycleEdgeIndex != -1) {
32 // If there is both a conflict and a cycle, return the edge causing the conflict,
33 // which is the first one when traversing from the 'to' node
34 return new int[]{parents[to], to};
35 }
36 // If there is only a conflict, return the conflicting edge
37 return edges[conflictEdgeIndex];
38 }
39}
40
41class UnionFind {
42 private int[] parent;
43 private int count;
44
45 public UnionFind(int size) {
46 parent = new int[size];
47 for (int i = 0; i < size; ++i) {
48 parent[i] = i;
49 }
50 this.count = size;
51 }
52
53 public boolean union(int a, int b) {
54 int parentA = find(a);
55 int parentB = find(b);
56 // If 'a' and 'b' are already connected, cannot perform union operation
57 if (parentA == parentB) {
58 return false;
59 }
60 // Connect the sets by updating the parent
61 parent[parentA] = parentB;
62 --count; // Decrement the number of components in the UnionFind
63 return true;
64 }
65
66 public int find(int x) {
67 // Path compression: make paths shorter for the 'find' queries
68 if (parent[x] != x) {
69 parent[x] = find(parent[x]);
70 }
71 return parent[x];
72 }
73}
74
1#include <vector>
2#include <numeric>
3using namespace std;
4
5// Class UnionFind represents a data structure for disjoint-set operations.
6class UnionFind {
7public:
8 // p stores the parent of each element, n represents the number of elements.
9 vector<int> parent;
10 int num_sets;
11
12 // Constructor initializes a disjoint-set for n elements.
13 UnionFind(int n)
14 : num_sets(n)
15 , parent(n) {
16 // iota fills the parent vector with increasing values starting from 0,
17 // so each element is initially in its own set.
18 iota(parent.begin(), parent.end(), 0);
19 }
20
21 // Method to unite two sets. Returns true if a union was performed, else false.
22 bool unite(int a, int b) {
23 int parent_a = find(a), parent_b = find(b);
24 // If both elements have the same parent, they are already connected, so no union is performed.
25 if (parent_a == parent_b) return false;
26 // Assign one element's parent to the other, effectively merging the sets.
27 parent[parent_a] = parent_b;
28 // Decrement the count of disjoint sets.
29 --num_sets;
30 return true;
31 }
32
33 // Find method with path compression. Finds the representative of the set containing x.
34 int find(int x) {
35 if (parent[x] != x) {
36 // Recursively find the parent and perform path compression.
37 parent[x] = find(parent[x]);
38 }
39 return parent[x];
40 }
41};
42
43// Solution class contains methods to analyze the graph and find the redundant edge.
44class Solution {
45public:
46 // Method to find the redundant directed connection in a graph represented by the edges list.
47 vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
48 int num_edges = edges.size();
49 // p keeps track of direct parents for each node.
50 vector<int> direct_parents(num_edges + 1);
51 for (int i = 0; i <= num_edges; ++i) direct_parents[i] = i;
52 UnionFind uf(num_edges + 1);
53 int conflict_edge_idx = -1, cycle_edge_idx = -1;
54
55 // Iterate over the edges to find any cycle or conflict.
56 for (int i = 0; i < num_edges; ++i) {
57 int u = edges[i][0], v = edges[i][1];
58 // If v already has a parent, we have found a conflict.
59 if (direct_parents[v] != v) {
60 conflict_edge_idx = i;
61 } else {
62 // Assign parent for v.
63 direct_parents[v] = u;
64 // If the union operation indicates a cycle, record the current edge index.
65 if (!uf.unite(u, v)) {
66 cycle_edge_idx = i;
67 }
68 }
69 }
70
71 // If there's no conflict, the redundant connection must be part of a cycle.
72 if (conflict_edge_idx == -1) {
73 return edges[cycle_edge_idx];
74 }
75
76 // If a cycle exists when a conflict is found, we return the previous edge that caused the cycle with the conflicting node.
77 int v = edges[conflict_edge_idx][1];
78 if (cycle_edge_idx != -1) {
79 return {direct_parents[v], v};
80 }
81 // If there's only a conflict without a cycle, we return the conflicting edge.
82 return edges[conflict_edge_idx];
83 }
84};
85
1// Importing array manipulations from lodash for `fill` similar to `iota` in C++
2import * as _ from "lodash";
3
4// Store the parent of each element; n represents the number of elements.
5let parent: number[];
6let numSets: number;
7