685. Redundant Connection II

HardDepth-First SearchBreadth-First SearchUnion FindGraph

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) in edges. Track the potential conflict by checking if a node v 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 because u and v are already in the same set (have the same root).

Walkthrough of Implementation Steps:

Initialize an instance of UnionFind, a list p to track the direct parents, and variables conflict and cycle to None.
Iterate over the provided list of edges (u, v).
- Check if node v has more than one parent by testing if p[v] has been set to something other than itself. Record the index of the second edge as conflict if this is the case.
- Perform the union operation for each edge (u, v). If it returns False, set cycle to the current index as it signifies that adding this edge creates a cycle.
Now assess the recorded conflict and cycle.
- If no conflict is found, return the last edge that failed to union which is causing the cycle. (i.e. edges[cycle]).
- If a conflict exists but no cycle is detected, the conflict edge is the problematic one, so return edges[conflict].
- If both conflict and cycle 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].

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 Evaluator

Example 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.
Edge [1,3]:
- There is no conflict at p[3] because it’s equal to 3.
- Union(1, 3) is successful.
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 set conflict = 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 set cycle = 3.

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
8// Initialize a disjoint-set for n elements.
9function initializeUnionFind(n: number): void {
10    numSets = n;
11    parent = _.fill(Array(n), 0).map((_, index) => index);
12}
13
14// Unite two sets. Returns true if a union was performed, otherwise false.
15function unite(a: number, b: number): boolean {
16    let parentA = find(a), parentB = find(b);
17    if (parentA == parentB) return false;
18    parent[parentA] = parentB;
19    numSets--;
20    return true;
21}
22
23// Find with path compression. Finds the representative of the set containing x.
24function find(x: number): number {
25    // Base case: if the element's parent is itself, it is the representative.
26    if (parent[x] != x) {
27        // Recursively find the parent and perform path compression.
28        parent[x] = find(parent[x]);
29    }
30    return parent[x];
31}
32
33// Find the redundant directed connection in a graph represented by the edges list.
34function findRedundantDirectedConnection(edges: number[][]): number[] {
35    // Variables to keep track of the state during the analysis.
36    let numEdges = edges.length;
37    let directParents: number[] = _.fill(Array(numEdges + 1), 0).map((_, index) => index);
38    initializeUnionFind(numEdges + 1);
39    let conflictEdgeIdx: number = -1, cycleEdgeIdx: number = -1;
40
41    // Iterate over the edges to find any cycle or conflict.
42    edges.forEach(([u, v], idx) => {
43        // If v already has a parent, a conflict is found.
44        if (directParents[v] != v) {
45            conflictEdgeIdx = idx;
46        } else {
47            // Assign the direct parent for v.
48            directParents[v] = u;
49            // If the union operation indicates a cycle, record the current edge index.
50            if (!unite(u, v)) {
51                cycleEdgeIdx = idx;
52            }
53        }
54    });
55
56    // If no conflict, the redundant connection is part of a cycle.
57    if (conflictEdgeIdx == -1) {
58        return edges[cycleEdgeIdx];
59    }
60
61    // If a cycle exists when a conflict is found, return the edge creating the cycle with the conflicting node.
62    let conflictV = edges[conflictEdgeIdx][1];
63    if (cycleEdgeIdx != -1) {
64        return [directParents[conflictV], conflictV];
65    }
66
67    // If there's only a conflict without a cycle, return the conflicting edge.
68    return edges[conflictEdgeIdx];
69}
70
71// Example Usage:
72const edges = [[1,2], [1,3], [2,3]];
73const redundantEdge = findRedundantDirectedConnection(edges);
74console.log(redundantEdge); // Output will be the redundant edge from the input graph.
75

Time and Space Complexity

The given code includes a UnionFind data structure and a Solution class that determines the redundant directed connection in a graph.

Time Complexity:

Initializing the UnionFind instance with self.p = list(range(n)) (where n is the number of edges) takes O(n) time.
The find() function of the UnionFind structure uses path compression which results in almost constant time complexity O(alpha(n)) for each call, where alpha is the inverse Ackermann function and is a very slowly growing function.
The union() function calls find() twice which takes O(alpha(n)) time and has an additional constant time overhead.
The for loop in the findRedundantDirectedConnection method iterates through each edge exactly once, resulting in O(n) iterations.
Inside the loop, the main operations are if p[v] != v (which is O(1)) and calls to the uf.union(u, v) (each being O(alpha(n))).

Given that the Ackermann function grows so slowly, O(alpha(n)) can be considered almost constant for all practical purposes. Therefore, the time complexity of the entire function is dominated by the for loop, leading to O(n).

Space Complexity:

The UnionFind instance has space complexity O(n) due to the parent array self.p.
The p list in the Solution class also has a space complexity of O(n).
The variables conflict and cycle are constant space overheads and do not depend on the size of the input.

Overall, the space complexity of the code is O(n), where n is the number of edges.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know