Description
You are given an integer n, representing n nodes numbered from 0 to n - 1 and a list of edges, where edges[i] = [ui, vi, si, musti]:
uiandviindicates an undirected edge between nodesuiandvi.siis the strength of the edge.mustiis an integer (0 or 1). Ifmusti == 1, the edge must be included in the spanning tree. These edges cannot be upgraded.
You are also given an integer k, the maximum number of upgrades you can perform. Each upgrade doubles the strength of an edge, and each eligible edge (with musti == 0) can be upgraded at most once.
The stability of a spanning tree is defined as the minimum strength score among all edges included in it.
Return the maximum possible stability of any valid spanning tree. If it is impossible to connect all nodes, return -1.
Note: A spanning tree of a graph with n nodes is a subset of the edges that connects all nodes together (i.e. the graph is connected) without forming any cycles, and uses exactly n - 1 edges.
Example 1:
Input: n = 3, edges = [[0,1,2,1],[1,2,3,0]], k = 1
Output: 2
Explanation:
- Edge
[0,1]with strength = 2 must be included in the spanning tree. - Edge
[1,2]is optional and can be upgraded from 3 to 6 using one upgrade. - The resulting spanning tree includes these two edges with strengths 2 and 6.
- The minimum strength in the spanning tree is 2, which is the maximum possible stability.
Example 2:
Input: n = 3, edges = [[0,1,4,0],[1,2,3,0],[0,2,1,0]], k = 2
Output: 6
Explanation:
- Since all edges are optional and up to
k = 2upgrades are allowed. - Upgrade edges
[0,1]from 4 to 8 and[1,2]from 3 to 6. - The resulting spanning tree includes these two edges with strengths 8 and 6.
- The minimum strength in the tree is 6, which is the maximum possible stability.
Example 3:
Input: n = 3, edges = [[0,1,1,1],[1,2,1,1],[2,0,1,1]], k = 0
Output: -1
Explanation:
- All edges are mandatory and form a cycle, which violates the spanning tree property of acyclicity. Thus, the answer is -1.
Constraints:
2 <= n <= 1051 <= edges.length <= 105edges[i] = [ui, vi, si, musti]0 <= ui, vi < nui != vi1 <= si <= 105mustiis either0or1.0 <= k <= n- There are no duplicate edges.
Solutions
The code solves a graph connectivity problem using a Union-Find data structure. It starts by processing all required edges to build mandatory connections, returning -1 if this creates a contradiction; then it sorts remaining edges by weight in descending order and greedily merges components, doubling the weight of edges that complete connections within the first k merges, while tracking the minimum weight encountered. The union function efficiently joins two components by managing their root pointers, returning true if it successfully merged two separate groups or false if they were already connected. Finally, if the graph isn't fully connected after processing all edges, it returns -1; otherwise, it returns the minimum weight found during the merging process.
/**
* @param {number} n
* @param {number[][]} edges
* @param {number} k
* @return {number}
*/
var maxStability = function (n, edges, k) {
// not solved, tried MST but couldn't do it
let groups = new Int32Array(n).fill(-1);
let totalGroups = n;
let minimum = Infinity;
for (let [v1, v2, w, required] of edges) {
if (required) {
if (!union(v1, v2, groups)) {
return -1;
}
--totalGroups;
minimum = Math.min(minimum, w);
}
}
edges.sort((a, b) => b[2] - a[2]);
for (let i = 0; i < edges.length && totalGroups > 1; ++i) {
let [v1, v2, w, required] = edges[i];
if (union(v1, v2, groups)) {
let remaining = totalGroups - 1;
if (remaining <= k) {
w *= 2;
}
minimum = Math.min(minimum, w)
--totalGroups
}
}
if (totalGroups > 1) {
return -1;
}
return minimum;
};
// return true if we've joined 2 groups, false if they're in the same group.
function union(v1, v2, groups) {
function findRoot(g) {
while (groups[g] !== g) {
g = groups[g];
}
return g;
}
if (groups[v1] < 0 && groups[v2] < 0) {
groups[v1] = v1;
groups[v2] = v1;
return true;
}
if (groups[v1] >= 0 && groups[v2] >= 0) {
let g1 = findRoot(groups[v1]);
let g2 = findRoot(groups[v2]);
groups[g1] = g2;
return g1 !== g2;
}
if (groups[v2] >= 0) {
groups[v1] = v2;
} else {
groups[v2] = v1;
}
return true;
}