Dare2Solve
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.
Union-Find Data Structure:
Edge Classification:
Union Operations:
Count Operations:
Validation:
groups == 1
in Union-Find for both).Result Calculation:
total_edges - count
.groups > 1
), return -1
indicating the graph cannot be fully traversed by both after removing edges.class UnionFind {
constructor(n) {
this.parent = new Array(n).fill().map((_, i) => i);
this.groups = n;
}
constructor(n)
: Initializes the Union-Find data structure with n
nodes.
this.parent
: An array where this.parent[i]
points to the parent of node i
. Initially, each node is its own parent.this.groups
: Keeps track of the number of connected components, initialized to n
because initially, each node is its own component. find(i) {
if (this.parent[i] !== i) {
this.parent[i] = this.find(this.parent[i]);
}
return this.parent[i];
}
find(i)
):
i
.i
, all nodes along the path are connected directly to the root to flatten the structure, optimizing future queries. 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(i, j)
):
i
and j
.i
and j
(rootI
and rootJ
).rootI
and rootJ
are different (indicating i
and j
are in different sets), rootJ
is made a child of rootI
(this.parent[rootJ] = rootI
), effectively merging the sets.groups
count as the number of connected components decreases by one after a successful union.true
if i
and j
were in different sets and were successfully united; otherwise, returns false
.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;
alice
and bob
are instances of the UnionFind
class, initialized with n
nodes each. These will track connectivity for edges that Alice and Bob can respectively traverse.count
initialized to 0
will track the number of edges that can be removed.for (let [type, u, v] of edges) {
if (type === 3 && alice.union(u, v) && bob.union(u, v)) {
count++;
}
}
edges
array).[type, u, v]
:
u
and v
in both alice
and bob
.alice.union(u, v)
and bob.union(u, v)
return true
(indicating successful unions), increment the count
variable to track removable edges.for (let [type, u, v] of edges) {
if ((type === 1 && alice.union(u, v)) || (type === 2 && bob.union(u, v))) {
count++;
}
}
edges
array) again.[type, u, v]
:
u
and v
in alice
for type 1 and in bob
for type 2.alice.union(u, v)
or bob.union(u, v)
returns true
, increment the count
variable to track removable edges. if (alice.groups === 1 && bob.groups === 1) {
return edges.length - count;
} else {
return -1;
}
};
alice.groups === 1
) and Bob (bob.groups === 1
) can fully traverse the graph.edges.length - count
, which gives the maximum number of removable edges while ensuring the graph remains fully traversable by both.-1
indicating it's impossible for both to traverse the graph fully even after removing edges.class UnionFind {
public:
vector<int> 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<vector<int>>& 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;
}
}
};
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
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;
}
}
}
/**
* @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;
}
}
}