Created
March 12, 2026 15:40
-
-
Save tatsuyax25/7791597d23e87ef0377ed608755f3187 to your computer and use it in GitHub Desktop.
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]: ui and vi indicates an undirected edge between nodes ui and vi.
si is the strength of the edge.
musti is an integer
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * @param {number} n | |
| * @param {number[][]} edges | |
| * @param {number} k | |
| * @return {number} | |
| */ | |
| var maxStability = function (n, edges, k) { | |
| // ----------------------------- | |
| // Disjoint Set Union (Union-Find) | |
| // ----------------------------- | |
| class DSU { | |
| constructor(n) { | |
| this.parent = Array.from({ length: n }, (_, i) => i); | |
| this.size = Array(n).fill(1); | |
| this.components = n; // track how many connected components remain | |
| } | |
| find(x) { | |
| if (this.parent[x] !== x) { | |
| this.parent[x] = this.find(this.parent[x]); | |
| } | |
| return this.parent[x]; | |
| } | |
| union(a, b) { | |
| let pa = this.find(a); | |
| let pb = this.find(b); | |
| if (pa === pb) return false; // already connected → would form a cycle | |
| // union by size | |
| if (this.size[pa] < this.size[pb]) { | |
| [pa, pb] = [pb, pa]; | |
| } | |
| this.parent[pb] = pa; | |
| this.size[pa] += this.size[pb]; | |
| this.components--; | |
| return true; | |
| } | |
| } | |
| // --------------------------------------------------------- | |
| // check(X): can we build a spanning tree with min edge ≥ X? | |
| // --------------------------------------------------------- | |
| function canAchieve(X) { | |
| const dsu = new DSU(n); | |
| let upgradesLeft = k; | |
| // 1️⃣ First, process mandatory edges | |
| for (const [u, v, s, must] of edges) { | |
| if (must === 1) { | |
| // mandatory edges cannot be upgraded | |
| if (s < X) return false; // impossible to reach threshold | |
| // if union fails → cycle among mandatory edges → invalid | |
| if (!dsu.union(u, v)) return false; | |
| } | |
| } | |
| // 2️⃣ Process optional edges | |
| // We separate them into: | |
| // - usable without upgrade | |
| // - usable only with upgrade | |
| const noUpgrade = []; | |
| const needUpgrade = []; | |
| for (const [u, v, s, must] of edges) { | |
| if (must === 1) continue; // already handled | |
| if (s >= X) { | |
| noUpgrade.push([u, v]); | |
| } else if (s * 2 >= X) { | |
| needUpgrade.push([u, v]); | |
| } | |
| // else: cannot reach X even with upgrade → ignore | |
| } | |
| // 3️⃣ Greedily use edges that need NO upgrade first | |
| for (const [u, v] of noUpgrade) { | |
| dsu.union(u, v); | |
| } | |
| // 4️⃣ Then use edges that require ONE upgrade | |
| for (const [u, v] of needUpgrade) { | |
| if (upgradesLeft === 0) break; | |
| if (dsu.union(u, v)) { | |
| upgradesLeft--; | |
| } | |
| } | |
| // 5️⃣ Check if we formed a spanning tree | |
| return dsu.components === 1; | |
| } | |
| // ------------------------------------ | |
| // Binary search on the answer (stability) | |
| // ------------------------------------ | |
| let left = 1; | |
| let right = 200000; // max possible strength after upgrade | |
| let best = -1; | |
| while (left <= right) { | |
| const mid = Math.floor((left + right) / 2); | |
| if (canAchieve(mid)) { | |
| best = mid; // mid is achievable → try higher | |
| left = mid + 1; | |
| } else { | |
| right = mid - 1; // mid not achievable → go lower | |
| } | |
| } | |
| return best; | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment