3720. Minimize The Maximum Edge Weight Of Graph¶

3720. Minimize the Maximum Edge Weight of Graph

Medium

You are given two integers, n and threshold, as well as a directed weighted graph of n nodes numbered from 0 to n - 1. The graph is represented by a 2D integer array edges, where edges[i] = [A_i, B_i, W_i] indicates that there is an edge going from node A_i to node B_i with weight W_i.

You have to remove some edges from this graph (possibly none), so that it satisfies the following conditions:

Node 0 must be reachable from all other nodes.
The maximum edge weight in the resulting graph is minimized.
Each node has at most threshold outgoing edges.

Return the minimum possible value of the maximum edge weight after removing the necessary edges. If it is impossible for all conditions to be satisfied, return -1.

Example 1:

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

Output: 1

Explanation:

Remove the edge 2 -> 0. The maximum weight among the remaining edges is 1.

Example 2:

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

Output: -1

Explanation:

It is impossible to reach node 0 from node 2.

Example 3:

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

Output: 2

Explanation:

Remove the edges 1 -> 3 and 1 -> 4. The maximum weight among the remaining edges is 2.

Example 4:

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

Output: -1

Constraints:

2 <= n <= 10⁵
1 <= threshold <= n - 1
1 <= edges.length <= min(10⁵, n * (n - 1) / 2).
edges[i].length == 3
0 <= A_i, B_i < n
A_i != B_i
1 <= W_i <= 10⁶
There may be multiple edges between a pair of nodes, but they must have unique weights.

Solution¶

class Solution {
    private ArrayList<ArrayList<Pair>> Revadj;
    static class Pair {
        int node, weight;
        public Pair(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
        @Override
        public String toString() {
            return "(" + node + " " + weight + ")";
        }
    }
    public int minMaxWeight(int n, int[][] edges, int threshold) {
        Revadj = new ArrayList<>();
        for (int i = 0; i <= n + 1; i++) Revadj.add(new ArrayList<>());
        for (int edge[] : edges) {
            int u = edge[0], v = edge[1], wt = edge[2];
            Revadj.get(v).add(new Pair(u, wt));
        }
        if (check(n) == false) return -1;
        int dist[] = new int[n + 1];
        Arrays.fill(dist, (int)(1e9));
        dist[0] = 0;
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(0, 0));
        while (q.size() > 0) {
            int u = q.peek().node;
            int curr_max = q.peek().weight;
            q.poll();
            for (int i = 0; i < Revadj.get(u).size(); i++) {
                int v = Revadj.get(u).get(i).node;
                int wt = Revadj.get(u).get(i).weight;
                if (dist[v] > Math.max(wt, curr_max)) {
                    dist[v] = Math.max(wt, curr_max);
                    q.offer(new Pair(v, dist[v]));
                }
            }
        }
        int maxi = dist[0];
        for (int i = 0; i < n; i++) maxi = Math.max(maxi, dist[i]);
        return maxi;
    }
    private boolean check(int n) {
        int vis[] = new int[n];
        ArrayList<Integer> nodes = new ArrayList<>();
        dfs(0, vis, nodes);
        return nodes.size() == n;
    }
    private void dfs(int u, int vis[], ArrayList<Integer> nodes) {
        nodes.add(u);
        vis[u] = 1;
        for (int i = 0; i < Revadj.get(u).size(); i++) {
            int v = Revadj.get(u).get(i).node;
            if (vis[v] == 0) dfs(v, vis, nodes);
        }
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]