1579. Remove Max Number of Edges to Keep Graph Fully Traversable
Problem Description
Alice and Bob have a special undirected graph that can only be traversed by them according to the types of edges it has. There are three types of edges in this graph:
- Type 1 edges can only be traversed by Alice.
- Type 2 edges can only be traversed by Bob.
- Type 3 edges can be traversed by both Alice and Bob.
This graph is represented by an array of edges where each edge is expressed as [type_i, u_i, v_i]. Here, type_i indicates the type of the edge, while u_i and v_i are the nodes that this edge connects.
The objective is to determine the maximum number of edges that can be removed from the graph while still allowing Alice and Bob to traverse the entire graph. To "traverse the entire graph" means that Alice and Bob can reach all nodes from any starting node. If there's no way to traverse the entire graph by both Alice and Bob after the removal of any edges, the answer should be -1.
Intuition
The solution to the problem relies on the concept of 'union find' data structures which helps in keeping track of connected components in a graph. Initially, we consider all nodes as separate components. The objective is to connect these components step by step, minimizing the number of connections, which implies maximizing the removal of unnecessary edges.
To solve the problem, we create two separate union find instances—one for Alice and one for Bob. We start by looking at the Type 3 edges first because these edges are usable by both Alice and Bob. When we encounter a Type 3 edge, we attempt to merge the components in both Alice's and Bob's union find structures. If the components are already merged in both, it means that edge is not necessary for traversal, and it can be removed. After dealing with Type 3 edges, we individually process Type 1 and Type 2 edges for Alice and Bob, respectively.
The intuition here is that if we can't connect all nodes after processing all edges, then it's impossible for Alice or Bob to traverse the entire graph, in which case we return -1. However, if after processing all the edges Alice and Bob are each able to traverse the entire graph, we return the count of the number of edges we decided to remove.
Learn more about Union Find and Graph patterns.
Solution Approach
The Reference Solution Approach mentions 'Union find', which is a key data structure used for this problem. Let's delve into how Union Find, also known as Disjoint Set Union (DSU), is used to solve this problem.
Union Find Data Structure
The Union Find data structure consists of two primary operations:
findoperation determines which set a particular element belongs to. With path compression, it can perform nearly constant time complexity.unionoperation merges two sets together if they are not already merged. Union by size ensures that the tree remains balanced, leading to fasterunionoperations.
Union Find Class Implementation
We create a Union Find class, UnionFind, with the following characteristics:
- An array
pto store the parent of each node, initialized to each node being its own parent. - An array
sizewhich stores the sizes of the components represented by the roots, used to keep the tree balanced during union operation. - A
cntvariable that keeps track of the count of separate components.
find Method
When the find method is called with a node x, it checks whether x is its own parent (leader of the component). If not, it recursively updates the parent of x to be the root of the component (path compression), thereby flattening the tree structure for future accesses.
union Method
The union method takes in two nodes a and b, finds their respective roots and if they belong to different components, joins the smaller component under the larger one (union by size). This not only helps in keeping the tree depth minimal but also reduces the time complexity of future find operations.
Algorithm
- Initialize two instance of UnionFind, one for Alice and another for Bob, named
ufaandufbrespectively. - Define a variable
ansto count the number of edges that can be removed.
Processing Type 3 Edges
- Iterate through the given
edges. For edges oftype3:- If union of the two connected nodes (u,v) is successful in
ufaandufb, no action is taken (the edge is needed). - If union is not successful (already in the same component), increment
ansbecause this edge can be removed.
- If union of the two connected nodes (u,v) is successful in
Processing Type 1 and Type 2 Edges
- Iterate through the given
edgesagain.- For edges of
type1, try to perform union inufa. If the edge cannot help in further union (meaning that edge is redundant), incrementans. - Similarly, for edges of
type2, perform union inufband if the edge is not needed, incrementans.
- For edges of
Conclusion
- At the end, check if both Alice and Bob can traverse the whole graph; this is indicated by
cntbeing 1 for bothufaandufb. If yes, returnansas the maximum number of edges that can be removed. Otherwise, return-1indicating it’s not possible for Alice and Bob to traverse the entire graph after removing the edges.
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 simple example where the following edges are given for the graph:
Edges = [[3, 1, 2], [3, 2, 3], [1, 1, 3], [2, 2, 4]]
Now, using the solution approach described above, we will determine the maximum number of edges that can be removed while ensuring both Alice and Bob can traverse the entire graph.
-
We initialize two instances of UnionFind, one for Alice (
ufa) and one for Bob (ufb). Also, we define a variableansand set it to 0, which will count the number of removable edges. -
We start by considering the Type 3 edges. Here they are
[[3, 1, 2], [3, 2, 3]].- For the edge [3, 1, 2], we attempt to union node 1 and 2 in both
ufaandufb. Since they are separate components, they're merged, andansremains 0. - Next, for [3, 2, 3], we again attempt to union in both
ufaandufb. They are not in the same component, so we merge them, andansremains 0.
- For the edge [3, 1, 2], we attempt to union node 1 and 2 in both
-
Now, we process the Type 1 and Type 2 edges. Edges [1, 1, 3] and [2, 2, 4] are now considered.
- For the edge [1, 1, 3], we attempt to union node 1 and 3 in
ufa. However, they are already connected through the Type 3 edge previously addressed, so this edge is not needed andansis incremented to 1. - For the edge [2, 2, 4], since node 4 is not connected to anything in
ufb, it is combined with node 2, andansstays at 1.
- For the edge [1, 1, 3], we attempt to union node 1 and 3 in
-
After processing all edges, we check if both
ufaandufbhave covered all nodes. In this case, both have 3 nodes connected through edges, which means both Alice and Bob can traverse the entire graph. -
Since Alice and Bob can traverse the entire graph, we return
ansas the result. Therefore, the maximum number of edges that can be removed is1in this example. If it was not possible for both Alice and Bob to traverse the entire graph, we would have returned-1.
Solution Implementation
1class UnionFind:
2 def __init__(self, size):
3 # Initializes the UnionFind structure.
4 # Each node is its own parent at first, and the size of each set is 1.
5 # `count` tracks the number of disjoint sets.
6 self.parent = list(range(size))
7 self.set_size = [1] * size
8 self.count = size
9
10 def find(self, node):
11 # Recursively finds the root parent of a node.
12 # Applies path compression by linking the node directly to the root parent.
13 if self.parent[node] != node:
14 self.parent[node] = self.find(self.parent[node])
15 return self.parent[node]
16
17 def union(self, node1, node2):
18 # Merges the sets of node1 and node2.
19 # If they already share the same parent, no union is performed, returns False.
20 # Otherwise, the smaller set is merged into the larger one, and True is returned.
21 root1, root2 = self.find(node1 - 1), self.find(node2 - 1)
22 if root1 == root2:
23 return False
24 if self.set_size[root1] > self.set_size[root2]:
25 self.parent[root2] = root1
26 self.set_size[root1] += self.set_size[root2]
27 else:
28 self.parent[root1] = root2
29 self.set_size[root2] += self.set_size[root1]
30 self.count -= 1
31 return True
32
33
34class Solution:
35 def maxNumEdgesToRemove(self, num_nodes: int, edges: List[List[int]]) -> int:
36 # Initializes two UnionFind instances, one for Alice and one for Bob.
37 alice_union_find = UnionFind(num_nodes)
38 bob_union_find = UnionFind(num_nodes)
39 num_edges_removed = 0
40
41 # Adds type 3 edges (common to both Alice and Bob).
42 # If an edge cannot be added because it does not merge two different sets,
43 # it is considered redundant and can be removed.
44 for edge_type, node1, node2 in edges:
45 if edge_type == 3:
46 if not alice_union_find.union(node1, node2):
47 num_edges_removed += 1
48 else:
49 # Add the edge for Bob as well since it's a common edge.
50 bob_union_find.union(node1, node2)
51
52 # Adds type 1 and type 2 edges (specific to Alice and Bob respectively).
53 # If an edge cannot be added because it does not merge two different sets,
54 # it is considered redundant and can be removed.
55 for edge_type, node1, node2 in edges:
56 if edge_type == 1:
57 # If the edge cannot be added, increment the removal count.
58 if not alice_union_find.union(node1, node2):
59 num_edges_removed += 1
60 elif edge_type == 2:
61 if not bob_union_find.union(node1, node2):
62 num_edges_removed += 1
63
64 # The graph is fully connected for both Alice and Bob only if both have exactly one set.
65 # In such a case, return the number of edges removed, otherwise return -1.
66 if alice_union_find.count == 1 and bob_union_find.count == 1:
67 return num_edges_removed
68 else:
69 return -1
701class UnionFind {
2 private int[] parent; // Parent array to represent the disjoint set forest
3 private int[] size; // Size array to count the number of elements in each set
4 public int count; // Count of distinct sets
5
6 // Constructor initializes each node in its own set with size 1
7 public UnionFind(int n) {
8 parent = new int[n];
9 size = new int[n];
10 for (int i = 0; i < n; ++i) {
11 parent[i] = i;
12 size[i] = 1;
13 }
14 count = n;
15 }
16
17 // Find the root of the set in which element x is present
18 // Uses path compression for efficiency
19 public int find(int x) {
20 if (parent[x] != x) {
21 parent[x] = find(parent[x]); // path compression
22 }
23 return parent[x];
24 }
25
26 // Union function to merge sets containing elements 'a' and 'b'
27 // Returns true if a merge happened, false if already in the same set
28 public boolean union(int a, int b) {
29 int rootA = find(a - 1), rootB = find(b - 1);
30 if (rootA == rootB) {
31 return false; // Already in the same set
32 }
33 if (size[rootA] > size[rootB]) { // Merge smaller set into larger set
34 parent[rootB] = rootA;
35 size[rootA] += size[rootB];
36 } else {
37 parent[rootA] = rootB;
38 size[rootB] += size[rootA];
39 }
40 --count; // Decrease the number of sets
41 return true;
42 }
43}
44
45class Solution {
46 // Function to find the maximum number of edges that can be removed from the input graph
47 // Returns -1 if Alice and Bob cannot both traverse the entire graph
48 public int maxNumEdgesToRemove(int n, int[][] edges) {
49 UnionFind aliceSet = new UnionFind(n);
50 UnionFind bobSet = new UnionFind(n);
51 int numEdgesToRemove = 0; // Tracks the number of edges we can remove
52
53 // First, process type 3 edges which are shared by Alice and Bob
54 for (int[] edge : edges) {
55 int type = edge[0], u = edge[1], v = edge[2];
56 if (type == 3) {
57 // Union operations for shared edges. If union operation fails
58 // (i.e., edge is redundant), increment numEdgesToRemove.
59 if (!aliceSet.union(u, v)) {
60 numEdgesToRemove++;
61 } else {
62 bobSet.union(u, v); // We can safely ignore return val since aliceSet succeeded
63 }
64 }
65 }
66
67 // Process Alice-only and Bob-only edges
68 for (int[] edge : edges) {
69 int type = edge[0], u = edge[1], v = edge[2];
70 if (type == 1 && !aliceSet.union(u, v)) { // Alice-only edge
71 numEdgesToRemove++; // If edge is already connected then increment the removal count
72 }
73 if (type == 2 && !bobSet.union(u, v)) { // Bob-only edge
74 numEdgesToRemove++; // If edge is already connected then increment the removal count
75 }
76 }
77
78 // If both Alice's and Bob's sets are fully connected (i.e., count is 1 for both),
79 // return number of edges removed. Otherwise, return -1 since they cannot
80 // both traverse the entire graph.
81 return (aliceSet.count == 1 && bobSet.count == 1) ? numEdgesToRemove : -1;
82 }
83}
841#include <vector>
2#include <numeric>
3using namespace std;
4
5// Union-Find Disjoint Set implementation
6class UnionFind {
7public:
8 vector<int> parents; // Store the parent of each element
9 vector<int> sizes; // Store the size of each set
10 int count; // Counter for the number of disjoint sets
11
12 // Constructor to initialize Union-Find structure with `n` elements
13 UnionFind(int n): count(n), parents(n), sizes(n, 1) {
14 // Initialize parents to themselves and
15 // sizes to 1 for each element
16 iota(parents.begin(), parents.end(), 0);
17 }
18
19 // Function to merge the sets containing elements `a` and `b`
20 bool unite(int a, int b) {
21 int parentA = find(a - 1);
22 int parentB = find(b - 1);
23 if (parentA == parentB) {
24 // `a` and `b` are already in the same set
25 return false;
26 }
27 if (sizes[parentA] > sizes[parentB]) {
28 // Merge the smaller set into the larger set
29 parents[parentB] = parentA;
30 sizes[parentA] += sizes[parentB];
31 } else {
32 // Merge the smaller or equal size set into the other
33 parents[parentA] = parentB;
34 sizes[parentB] += sizes[parentA];
35 }
36 --count; // Reduce the count of disjoint sets
37 return true;
38 }
39
40 // Function to find the root parent of element `x`
41 int find(int x) {
42 if (parents[x] != x) {
43 // Path compression step to flatten tree
44 parents[x] = find(parents[x]);
45 }
46 return parents[x];
47 }
48};
49
50// Solution class for the specific problem
51class Solution {
52public:
53 // Function to find the maximum number of edges that can be removed
54 int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
55 UnionFind ufa(n); // Union-Find for Alice
56 UnionFind ufb(n); // Union-Find for Bob
57 int removalCount = 0; // Counter for the number of edges removed
58
59 // First, we deal with type 3 edges, which benefit both Alice and Bob
60 for (auto& edge : edges) {
61 if (edge[0] == 3) {
62 bool united = ufa.unite(edge[1], edge[2]);
63 ufb.unite(edge[1], edge[2]); // Note: `unite` results should be the same for ufa and ufb
64 if (!united) {
65 // Edge not necessary, count it for removal
66 ++removalCount;
67 }
68 }
69 }
70
71 // Next, process type 1 and type 2 edges separately for Alice and Bob
72 for (auto& edge : edges) {
73 int type = edge[0], u = edge[1], v = edge[2];
74 if (type == 1) {
75 // Type 1 edges for Alice; increase removal count if not united
76 removalCount += !ufa.unite(u, v);
77 }
78 if (type == 2) {
79 // Type 2 edges for Bob; increase removal count if not united
80 removalCount += !ufb.unite(u, v);
81 }
82 }
83
84 // Check if both Alice and Bob have connected graphs
85 if (ufa.count == 1 && ufb.count == 1) {
86 // All vertices are connected for both, so return the removal count
87 return removalCount;
88 } else {
89 // Not all vertices are connected (one or both are disconnected)
90 return -1;
91 }
92 }
93};
941type UnionFind = {
2 parents: number[];
3 sizes: number[];
4 count: number;
5};
6
7// Initialize Union-Find structure with `n` elements
8function createUnionFind(n: number): UnionFind {
9 const parents = Array.from({ length: n }, (_, index) => index);
10 const sizes = new Array(n).fill(1);
11 return { parents, sizes, count: n };
12}
13
14// Find the root parent of element `x`
15function find(unionFind: UnionFind, x: number): number {
16 if (unionFind.parents[x] !== x) {
17 // Path compression step to flatten the hierarchy
18 unionFind.parents[x] = find(unionFind, unionFind.parents[x]);
19 }
20 return unionFind.parents[x];
21}
22
23// Merge the sets containing elements `a` and `b`
24function unite(unionFind: UnionFind, a: number, b: number): boolean {
25 let parentA = find(unionFind, a - 1);
26 let parentB = find(unionFind, b - 1);
27 if (parentA === parentB) {
28 // `a` and `b` are already in the same set
29 return false;
30 }
31 if (unionFind.sizes[parentA] > unionFind.sizes[parentB]) {
32 // Merge the smaller set into the larger set
33 unionFind.parents[parentB] = parentA;
34 unionFind.sizes[parentA] += unionFind.sizes[parentB];
35 } else {
36 // Merge the smaller or equal size set into the other one
37 unionFind.parents[parentA] = parentB;
38 unionFind.sizes[parentB] += unionFind.sizes[parentA];
39 }
40 unionFind.count--; // Reduce the count of disjoint sets
41 return true;
42}
43
44// Function to find the maximum number of edges that can be removed
45function maxNumEdgesToRemove(n: number, edges: number[][]): number {
46 let ufa = createUnionFind(n); // Union-Find for Alice
47 let ufb = createUnionFind(n); // Union-Find for Bob
48 let removalCount = 0; // Counter for the number of edges removed
49
50 // First, handle type 3 edges, which benefit both Alice and Bob
51 for (let edge of edges) {
52 if (edge[0] === 3) {
53 let unitedA = unite(ufa, edge[1], edge[2]);
54 unite(ufb, edge[1], edge[2]); // Should have the same result for ufb
55 if (!unitedA) {
56 // Edge is not necessary; increment removal count
57 removalCount++;
58 }
59 }
60 }
61
62 // Next, process type 1 and type 2 edges separately for Alice and Bob
63 for (let edge of edges) {
64 let type = edge[0], u = edge[1], v = edge[2];
65 if (type === 1) {
66 // Type 1 edges for Alice; increase removal count if not united
67 removalCount += !unite(ufa, u, v) ? 1 : 0;
68 } else if (type === 2) {
69 // Type 2 edges for Bob; increase removal count if not united
70 removalCount += !unite(ufb, u, v) ? 1 : 0;
71 }
72 }
73
74 // Check if both Alice and Bob have connected graphs
75 if (ufa.count === 1 && ufb.count === 1) {
76 // All vertices are connected for both, so return the removal count
77 return removalCount;
78 } else {
79 // Not all vertices are connected (one or both are disconnected)
80 return -1;
81 }
82}
83Time and Space Complexity
Time Complexity
The main time-consuming operations in this code are the two for loops that iterate over the edges and the find and union operations of the UnionFind data structure.
-
Initializing the UnionFind structure with
nelements takesO(n)time as it initializes two lists of lengthn. -
The
findoperation uses path compression which, in the amortized case, yields a time complexity close to constant timeO(1). However, without amortization and in the worst case without path compression, it could takeO(n). -
The
unionoperation also has an amortized time complexity ofO(1)since it potentially involves twofindoperations and simple assignment and arithmetic operations. -
The first
forloop iterates over all edges. If there areEedges of type 3, in the worst case, where the union operation might include traversing the height of the trees, this loop runs inO(E)time. Due to path compression and the balancing by size, this is typically much faster on average, but strictly speaking and not accounting for amortization, it'sO(E * alpha(n)), wherealpha(n)is the Inverse Ackermann function, which grows extremely slowly and is practically constant. -
The second
forloop is similar to the first one, it goes through all edges again and attempts to union them. This results in the same time complexity analysis as above.
Therefore, assuming E is the total number of edges, the total time complexity of the Solution.maxNumEdgesToRemove is O(E * alpha(n)), noting that for all practical purposes, alpha(n) can be considered a constant and thus the time complexity is effectively O(E).
Space Complexity
The space complexity is mainly due to the UnionFind data structure which holds two arrays p and size of length n and the inputs themselves.
-
The UnionFind structure uses
O(n)space because of the parent array and the size array, both of which havenelements. -
There is no additional space used that grows with the input size, except for the input
edgesthemselves, which is external and not part of the space complexity of this algorithm.
Therefore, the total space complexity of the Solution.maxNumEdgesToRemove is O(n) where n is the number of vertices.
Learn more about how to find time and space complexity quickly using problem constraints.
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
141public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
271function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27Recommended Readings
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!