3613. Minimize Maximum Component Cost

Description

You are given an undirected connected graph with n nodes labeled from 0 to n - 1 and a 2D integer array edges where edges[i] = [u_i, v_i, w_i] denotes an undirected edge between node u_i and node v_i with weight w_i, and an integer k.

You are allowed to remove any number of edges from the graph such that the resulting graph has at most k connected components.

The cost of a component is defined as the maximum edge weight in that component. If a component has no edges, its cost is 0.

Return the minimum possible value of the maximum cost among all components after such removals.

Example 1:

Input: n = 5, edges = [[0,1,4],[1,2,3],[1,3,2],[3,4,6]], k = 2

Output: 4

Explanation:

Remove the edge between nodes 3 and 4 (weight 6).
The resulting components have costs of 0 and 4, so the overall maximum cost is 4.

Example 2:

Input: n = 4, edges = [[0,1,5],[1,2,5],[2,3,5]], k = 1

Output: 5

Explanation:

No edge can be removed, since allowing only one component (k = 1) requires the graph to stay fully connected.
That single component’s cost equals its largest edge weight, which is 5.

Constraints:

1 <= n <= 5 * 10⁴
0 <= edges.length <= 10⁵
edges[i].length == 3
0 <= u_i, v_i < n
1 <= w_i <= 10⁶
1 <= k <= n
The input graph is connected.

Solutions

Solution 1: Sorting + Union-Find

If \(k = n\), it means all edges can be removed. In this case, all connected components are isolated nodes, and the maximum cost is 0.

Otherwise, we can sort all edges by weight in ascending order, then use a union-find data structure to maintain connected components.

We assume that initially all nodes are not connected, with each node being an independent connected component. Starting from the edge with the smallest weight, we try to add it to the current connected components. If the number of connected components becomes less than or equal to \(k\) after adding the edge, it means all remaining edges can be removed, and the weight of the current edge is the maximum cost we are looking for. We return this weight. Otherwise, we continue processing the next edge.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(n)\), where \(n\) is the number of nodes.

Python3JavaC++GoTypeScript

class Solution:
    def minCost(self, n: int, edges: List[List[int]], k: int) -> int:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        if k == n:
            return 0
        edges.sort(key=lambda x: x[2])
        cnt = n
        p = list(range(n))
        for u, v, w in edges:
            pu, pv = find(u), find(v)
            if pu != pv:
                p[pu] = pv
                cnt -= 1
                if cnt <= k:
                    return w
        return 0

class Solution {
    private int[] p;

    public int minCost(int n, int[][] edges, int k) {
        if (k == n) {
            return 0;
        }
        p = new int[n];
        Arrays.setAll(p, i -> i);
        Arrays.sort(edges, Comparator.comparingInt(a -> a[2]));
        int cnt = n;
        for (var e : edges) {
            int u = e[0], v = e[1], w = e[2];
            int pu = find(u), pv = find(v);
            if (pu != pv) {
                p[pu] = pv;
                if (--cnt <= k) {
                    return w;
                }
            }
        }
        return 0;
    }

    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}

class Solution {
public:
    int minCost(int n, vector<vector<int>>& edges, int k) {
        if (k == n) {
            return 0;
        }
        vector<int> p(n);
        ranges::iota(p, 0);
        ranges::sort(edges, {}, [](const auto& e) { return e[2]; });
        auto find = [&](this auto&& find, int x) -> int {
            if (p[x] != x) {
                p[x] = find(p[x]);
            }
            return p[x];
        };
        int cnt = n;
        for (const auto& e : edges) {
            int u = e[0], v = e[1], w = e[2];
            int pu = find(u), pv = find(v);
            if (pu != pv) {
                p[pu] = pv;
                if (--cnt <= k) {
                    return w;
                }
            }
        }
        return 0;
    }
};

func minCost(n int, edges [][]int, k int) int {
    p := make([]int, n)
    for i := range p {
        p[i] = i
    }

    var find func(int) int
    find = func(x int) int {
        if p[x] != x {
            p[x] = find(p[x])
        }
        return p[x]
    }

    if k == n {
        return 0
    }

    slices.SortFunc(edges, func(a, b []int) int {
        return a[2] - b[2]
    })

    cnt := n
    for _, e := range edges {
        u, v, w := e[0], e[1], e[2]
        pu, pv := find(u), find(v)
        if pu != pv {
            p[pu] = pv
            if cnt--; cnt <= k {
                return w
            }
        }
    }

    return 0
}

function minCost(n: number, edges: number[][], k: number): number {
    const p: number[] = Array.from({ length: n }, (_, i) => i);
    const find = (x: number): number => {
        if (p[x] !== x) {
            p[x] = find(p[x]);
        }
        return p[x];
    };

    if (k === n) {
        return 0;
    }

    edges.sort((a, b) => a[2] - b[2]);
    let cnt = n;
    for (const [u, v, w] of edges) {
        const pu = find(u),
            pv = find(v);
        if (pu !== pv) {
            p[pu] = pv;
            if (--cnt <= k) {
                return w;
            }
        }
    }
    return 0;
}

3613. Minimize Maximum Component Cost

Description

Solutions

Solution 1: Sorting + Union-Find

Comments