Problem of The Day: Remove Max Number of Edges to Keep Graph Fully Traversable
Problem Statement
Intuition
My first thought was that this problem revolves around using the Union-Find (or Disjoint Set Union) data structure. This data structure is particularly useful for handling connectivity problems, where we need to efficiently merge sets and find representatives of elements. Here, the goal is to determine the maximum number of edges that can be removed while still ensuring that both Alice and Bob can traverse the entire graph.
Approach
-
Union-Find Initialization:
- I initialized two Union-Find structures: one for Alice and one for Bob. This allows me to separately track the connected components for both Alice and Bob.
-
Processing Type 3 Edges:
- Type 3 edges can be used by both Alice and Bob. Hence, I first processed all type 3 edges and tried to add them to both Union-Find structures. If either Alice or Bob could use the edge to connect two components, I counted it as necessary.
-
Processing Type 1 and Type 2 Edges:
- Next, I processed type 1 edges (Alice only) and type 2 edges (Bob only). For each edge, I attempted to add it to the respective Union-Find structure. Again, if the edge was useful in connecting two components, I counted it as necessary.
-
Counting Removable Edges:
- The total number of edges minus the number of necessary edges gave me the number of removable edges.
-
Final Check:
- Finally, I checked if both Alice and Bob can traverse the entire graph using the number of connected components in their respective Union-Find structures. If both have only one component, then they can traverse the graph. If not, it’s not possible to keep the graph connected for both Alice and Bob, and I returned -1.
Complexity
- Time Complexity: The time complexity of this approach is (O(E \cdot \alpha(N))), where (E) is the number of edges and (\alpha) is the inverse Ackermann function, which is almost constant in practical scenarios.
- Space Complexity: The space complexity is (O(N)), where (N) is the number of nodes, due to the storage of parent and rank arrays in the Union-Find structures.
Code
class UnionFind:
def __init__(self, n):
self.root = list(range(n))
self.rank = [1] * n
self.num_of_components = n
def find(self, x):
if x == self.root[x]:
return x
self.root[x] = self.find(self.root[x])
return self.root[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
if self.rank[root_x] > self.rank[root_y]:
self.root[root_y] = root_x
self.rank[root_x] += 1
elif self.rank[root_x] < self.rank[root_y]:
self.root[root_x] = root_y
self.rank[root_y] += 1
else:
self.root[root_y] = root_x
self.rank[root_x] += 1
self.num_of_components -= 1
return 1
return 0
def isConnected(self, x, y):
return self.root[x] == self.root[y]
class Solution:
def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
aliceUF = UnionFind(n)
bobUF = UnionFind(n)
res = 0
required = 0
for edge_type, u, v in edges:
u, v = u - 1, v - 1
if edge_type == 3:
alice_union = aliceUF.union(u, v)
bob_union = bobUF.union(u, v)
val = alice_union or bob_union
required += val
for edge_type, u, v in edges:
u, v = u - 1, v - 1
if edge_type == 1:
required += aliceUF.union(u, v)
if edge_type == 2:
required += bobUF.union(u, v)
res = len(edges) - required
if aliceUF.num_of_components == 1 and bobUF.num_of_components == 1:
return res
return -1
Editorial
class UnionFind {
vector<int> representative;
vector<int> componentSize;
// Number of distinct components in the graph.
int components;
public:
// Initialize the list representative and componentSize
// Each node is representative of itself with size 1.
UnionFind(int n) {
components = n;
for (int i = 0; i <= n; i++) {
representative.push_back(i);
componentSize.push_back(1);
}
}
// Get the root of a node.
int findRepresentative(int x) {
if (representative[x] == x) {
return x;
}
// Path compression.
return representative[x] = findRepresentative(representative[x]);
}
// Perform the union of two components that belongs to node x and node y.
int performUnion(int x, int y) {
x = findRepresentative(x); y = findRepresentative(y);
if (x == y) {
return 0;
}
if (componentSize[x] > componentSize[y]) {
componentSize[x] += componentSize[y];
representative[y] = x;
} else {
componentSize[y] += componentSize[x];
representative[x] = y;
}
components--;
return 1;
}
// Returns true if all nodes get merged to one.
bool isConnected() {
return components == 1;
}
};
class Solution {
public:
int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
// Different objects for Alice and Bob.
UnionFind Alice(n), Bob(n);
int edgesRequired = 0;
// Perform union for edges of type = 3, for both Alice and Bob.
for (vector<int>& edge : edges) {
if (edge[0] == 3) {
edgesRequired += (Alice.performUnion(edge[1], edge[2]) | Bob.performUnion(edge[1], edge[2]));
}
}
// Perform union for Alice if type = 1 and for Bob if type = 2.
for (vector<int>& edge : edges) {
if (edge[0] == 1) {
edgesRequired += Alice.performUnion(edge[1], edge[2]);
} else if (edge[0] == 2) {
edgesRequired += Bob.performUnion(edge[1], edge[2]);
}
}
// Check if the Graphs for Alice and Bob have n - 1 edges or is a single component.
if (Alice.isConnected() && Bob.isConnected()) {
return edges.size() - edgesRequired;
}
return -1;
}
};
