Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Mandatory edges must form a forest and already cap the final stability because they cannot be upgraded. After joining that forest, prefer the strongest optional edges that connect different components. Among the chosen optional edges, upgrades are most useful on the weakest ones.

Approach

Use union-find to insert all mandatory edges. Reject immediately if one closes a cycle, and record their minimum strength. Sort optional edges by decreasing strength and apply Kruskal's rule, accepting an edge only when it joins different components.

Track the total number of accepted edges. Once that count exceeds n - 1 - k, treat subsequent accepted optional edges as upgraded and use twice their strength when updating the minimum. Thus the last, weakest up-to-k optional edges receive upgrades; mandatory edges never do.

Descending Kruskal maximizes the number of selected edges above every strength threshold, so its ordered optional strengths are no worse than those of any other feasible extension. Upgrading the weakest selected edges then maximizes the minimum effective strength. Return -1 if fewer than n - 1 edges were accepted; otherwise return the recorded minimum.

class UF:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if self.rank[px] < self.rank[py]:
            self.par[px] = py
        elif self.rank[py] < self.rank[px]:
            self.par[py] = px
        else:
            self.rank[px] += 1
            self.par[py] = px

class Solution:
    def maxStability(self, n: int, edges: List[List[int]], k: int) -> int:
        uf = UF(n)
        used = 0
        opt = []
        res = inf

        for x, y, s, m in edges:
            if m:
                if uf.find(x) == uf.find(y):
                    return -1
                uf.union(x, y)
                used += 1
                res = min(res, s)
            else:
                opt.append((x, y, s, m))

        opt.sort(key = lambda x: x[2], reverse = True)

        for i in range(len(opt)):
            x, y, s, m = opt[i]
            if uf.find(x) == uf.find(y):
                continue
            uf.union(x, y)
            used += 1
            if used <= n - 1 - k:
                res = min(res, s)
            else:
                res = min(res, s * 2)

        if used != n - 1:
            return -1

        return res

Complexity analysis

Let N be the vertex count and E the edge count. Time is O(N + Elog(E+1) + Ealpha(N)), including union-find initialization even when the graph is disconnected and E is much smaller than N. Auxiliary space is O(N+E) for union-find, optional edges and sorting. Path compression with union by rank bounds recursive find depth by O(log N) before compression.