🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem involves determining the maximum number of edges that can be removed while maintaining connectivity between all nodes in an undirected graph for both Alice and Bob. Different edge types restrict traversal permissions to Alice, Bob, or both.
Approach
- Union-Find Data Structure: - Use a Union-Find (Disjoint Set Union, DSU) data structure to manage connected components for Alice and Bob separately. - Each component in the Union-Find represents a set of nodes that are connected.
- Edge Classification: - Classify edges into three types based on their traversal permissions (Type 1 for Alice, Type 2 for Bob, Type 3 for both).
- Union Operations: - Perform union operations in the Union-Find data structure based on edge types: - For Type 3 edges, union nodes for both Alice and Bob. - For Type 1 and Type 2 edges, union nodes only for Alice or Bob respectively.
- Count Operations: - Count the number of edges removed while performing union operations. This count helps in determining the maximum removable edges.
- Validation:
- After processing all edges, check if both Alice and Bob have exactly one connected component each (i.e.,
groups == 1
in Union-Find for both). - Result Calculation:
- If both Alice and Bob have exactly one connected component each, calculate and return the maximum removable edges as
total_edges - count
. - If either Alice or Bob has more than one connected component (groups > 1
), return-1
indicating the graph cannot be fully traversed by both after removing edges.
Complexity
- Time Complexity: O(E * α(V)), where E is the number of edges and α is the inverse Ackermann function (nearly constant time for practical purposes in Union-Find).
- Space Complexity: O(V), where V is the number of nodes, primarily for storing parent pointers and sizes in Union-Find.
Code Explanation
Union-Find Data Structure Initialization
class UnionFind {
constructor(n) {
this.parent = new Array(n).fill().map((_, i) => i);
this.groups = n;
}
- UnionFind Class Initialization:
-
constructor(n)
: Initializes the Union-Find data structure withn
nodes. -this.parent
: An array wherethis.parent[i]
points to the parent of nodei
. Initially, each node is its own parent. -this.groups
: Keeps track of the number of connected components, initialized ton
because initially, each node is its own component.
Find Operation with Path Compression
find(i) {
if (this.parent[i] !== i) {
this.parent[i] = this.find(this.parent[i]);
}
return this.parent[i];
}
- Find Operation (
find(i)
): - Finds the root (or representative) of the set containing nodei
. - Uses path compression: When finding the root ofi
, all nodes along the path are connected directly to the root to flatten the structure, optimizing future queries.
Union Operation for Merging Sets
union(i, j) {
const rootI = this.find(i);
const rootJ = this.find(j);
if (rootI !== rootJ) {
this.parent[rootJ] = rootI;
this.groups--;
return true;
}
return false;
}
}
- Union Operation (
union(i, j)
): - Unites the sets containing nodesi
andj
. - Finds the roots ofi
andj
(rootI
androotJ
). - IfrootI
androotJ
are different (indicatingi
andj
are in different sets),rootJ
is made a child ofrootI
(this.parent[rootJ] = rootI
), effectively merging the sets. - Decreases thegroups
count as the number of connected components decreases by one after a successful union. - Returnstrue
ifi
andj
were in different sets and were successfully united; otherwise, returnsfalse
.
Main Function: `maxNumEdgesToRemove` Initialization
/**
* @param {number} n
* @param {number[][]} edges
* @returns {number}
*/
var maxNumEdgesToRemove = function (n, edges) {
const alice = new UnionFind(n);
const bob = new UnionFind(n);
let count = 0;
- Initialization:
-
alice
andbob
are instances of theUnionFind
class, initialized withn
nodes each. These will track connectivity for edges that Alice and Bob can respectively traverse. -count
initialized to0
will track the number of edges that can be removed.
Processing Type 3 Edges
for (let [type, u, v] of edges) {
if (type === 3 && alice.union(u, v) && bob.union(u, v)) {
count++;
}
}
- First Pass: Type 3 Edges:
- Loop through all edges (
edges
array). - For each edge[type, u, v]
: - Check if it's a type 3 edge (traversable by both Alice and Bob). - Attempt to union nodesu
andv
in bothalice
andbob
. - If bothalice.union(u, v)
andbob.union(u, v)
returntrue
(indicating successful unions), increment thecount
variable to track removable edges.
Processing Type 1 and Type 2 Edges
for (let [type, u, v] of edges) {
if ((type === 1 && alice.union(u, v)) || (type === 2 && bob.union(u, v))) {
count++;
}
}
- Second Pass: Type 1 and Type 2 Edges:
- Loop through all edges (
edges
array) again. - For each edge[type, u, v]
: - Check if it's a type 1 edge (Alice-only) or type 2 edge (Bob-only). - Attempt to union nodesu
andv
inalice
for type 1 and inbob
for type 2. - If eitheralice.union(u, v)
orbob.union(u, v)
returnstrue
, increment thecount
variable to track removable edges.
Result Evaluation
if (alice.groups === 1 && bob.groups === 1) {
return edges.length - count;
} else {
return -1;
}
};
- Result Evaluation:
- After processing all edges, check if both Alice (
alice.groups === 1
) and Bob (bob.groups === 1
) can fully traverse the graph. - If both conditions are true, returnedges.length - count
, which gives the maximum number of removable edges while ensuring the graph remains fully traversable by both. - If either Alice or Bob cannot fully traverse the graph (i.e., more than one connected component for either), return-1
indicating it's impossible for both to traverse the graph fully even after removing edges.
Code
C++
class UnionFind {
public:
vector parent;
int groups;
UnionFind(int n) : parent(n), groups(n - 1) {
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int find(int i) {
if (parent[i] != i) {
parent[i] = find(parent[i]);
}
return parent[i];
}
bool unionSets(int i, int j) {
int x = find(i);
int y = find(j);
if (x == y) {
return false;
} else {
parent[y] = x;
--groups;
return true;
}
}
};
class Solution {
public:
int maxNumEdgesToRemove(int n, vector>& edges) {
UnionFind alice(n), bob(n);
int count = 0;
for (const auto& edge : edges) {
int type = edge[0], u = edge[1] - 1, v = edge[2] - 1;
if (type == 3 && alice.unionSets(u, v) && bob.unionSets(u, v)) {
++count;
}
}
for (const auto& edge : edges) {
int type = edge[0], u = edge[1] - 1, v = edge[2] - 1;
if ((type == 1 && alice.unionSets(u, v)) || (type == 2 && bob.unionSets(u, v))) {
++count;
}
}
if (alice.groups == 0 && bob.groups == 0) {
return edges.size() - count;
} else {
return -1;
}
}
};
Python
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.groups = n - 1
def find(self, i):
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self, i, j):
x = self.find(i)
y = self.find(j)
if x == y:
return False
else:
self.parent[y] = x
self.groups -= 1
return True
class Solution:
def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
alice = UnionFind(n)
bob = UnionFind(n)
count = 0
for edge in edges:
type, u, v = edge[0], edge[1] - 1, edge[2] - 1
if type == 3 and alice.union(u, v) and bob.union(u, v):
count += 1
for edge in edges:
type, u, v = edge[0], edge[1] - 1, edge[2] - 1
if (type == 1 and alice.union(u, v)) or (type == 2 and bob.union(u, v)):
count += 1
if alice.groups == 0 and bob.groups == 0:
return len(edges) - count
else:
return -1
Java
class UnionFind {
int[] parent;
int groups;
UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
groups = n - 1;
}
int find(int i) {
if (parent[i] != i) {
parent[i] = find(parent[i]);
}
return parent[i];
}
boolean union(int i, int j) {
int x = find(i);
int y = find(j);
if (x == y) {
return false;
} else {
parent[y] = x;
groups--;
return true;
}
}
}
class Solution {
public int maxNumEdgesToRemove(int n, int[][] edges) {
UnionFind alice = new UnionFind(n);
UnionFind bob = new UnionFind(n);
int count = 0;
for (int[] edge : edges) {
int type = edge[0], u = edge[1] - 1, v = edge[2] - 1;
if (type == 3 && alice.union(u, v) && bob.union(u, v)) {
++count;
}
}
for (int[] edge : edges) {
int type = edge[0], u = edge[1] - 1, v = edge[2] - 1;
if ((type == 1 && alice.union(u, v)) || (type == 2 && bob.union(u, v))) {
++count;
}
}
if (alice.groups == 0 && bob.groups == 0) {
return edges.length - count;
} else {
return -1;
}
}
}
JavaScript
/**
* @param {number} n
* @param {number[][]} edges
* @returns {number}
*/
var maxNumEdgesToRemove = function (n, edges) {
const alice = new UnionFind(n), bob = new UnionFind(n);
let count = 0;
for (let [type, u, v] of edges) {
if (type === 3 && alice.union(u, v) && bob.union(u, v)) count++;
}
for (let [type, u, v] of edges) {
if (
(type === 1 && alice.union(u, v)) ||
(type === 2 && bob.union(u, v))
)
count++;
}
if (!bob.groups && !alice.groups) return edges.length - count;
else return -1;
};
/**
* @class UnionFind
* @param {number} n
*/
class UnionFind {
constructor(n) {
this.parent = new Array(n).fill().map((_, i) => i);
this.groups = n - 1;
}
/**
* @param {number} i
* @returns {number}
*/
find(i) {
if (this.parent[i] !== i) this.parent[i] = this.find(this.parent[i]);
return this.parent[i];
}
/**
* @param {number} i
* @param {number} j
* @returns {boolean}
*/
union(i, j) {
const x = this.find(i),
y = this.find(j);
if (x === y) return false;
else {
this.parent[y] = x;
this.groups--;
return true;
}
}
}