Skip to content

3419. Minimize the Maximum Edge Weight of Graph 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
 public:
  int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {
    constexpr int kMax = 1'000'000;
    vector<vector<pair<int, int>>> reversedGraph(n);

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      const int w = edge[2];
      reversedGraph[v].push_back({u, w});
    }

    int l = 1;
    int r = kMax + 1;

    while (l < r) {
      const int m = (l + r) / 2;
      if (dfs(reversedGraph, 0, m, vector<bool>(n)) == n)
        r = m;
      else
        l = m + 1;
    }

    return l == (kMax + 1) ? -1 : l;
  }

 private:
  // Returns the number of nodes reachable from u with weight <= m.
  int dfs(const vector<vector<pair<int, int>>>& reversedGraph, int u,
          int maxWeight, vector<bool>&& seen) {
    int res = 1;
    seen[u] = true;
    for (const auto& [v, w] : reversedGraph[u]) {
      if (w > maxWeight || seen[v])
        continue;
      res += dfs(reversedGraph, v, maxWeight, std::move(seen));
    }
    return res;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
  public int minMaxWeight(int n, int[][] pairs, int threshold) {
    final int MAX = 1_000_000;
    List<Pair<Integer, Integer>>[] reversedGraph = new List[n];

    for (int i = 0; i < n; i++)
      reversedGraph[i] = new ArrayList<>();

    for (int[] pair : pairs) {
      final int u = pair[0];
      final int v = pair[1];
      final int w = pair[2];
      reversedGraph[v].add(new Pair<>(u, w));
    }

    int l = 1;
    int r = MAX + 1;

    while (l < r) {
      final int m = (l + r) / 2;
      if (dfs(reversedGraph, 0, m, new boolean[n]) == n)
        r = m;
      else
        l = m + 1;
    }

    return l == (MAX + 1) ? -1 : l;
  }

  // Returns the number of nodes reachable from u with weight <= maxWeight.
  private int dfs(List<Pair<Integer, Integer>>[] reversedGraph, int u, int maxWeight,
                  boolean[] seen) {
    int res = 1;
    seen[u] = true;
    for (Pair<Integer, Integer> pair : reversedGraph[u]) {
      final int v = pair.getKey();
      final int w = pair.getValue();
      if (w > maxWeight || seen[v])
        continue;
      res += dfs(reversedGraph, v, maxWeight, seen);
    }
    return res;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
  def minMaxWeight(self, n: int, edges: list[list[int]], threshold: int) -> int:
    MAX = 1000000
    reversedGraph = [[] for _ in range(n)]

    for u, v, w in edges:
      reversedGraph[v].append((u, w))

    l = 1
    r = MAX + 1

    while l < r:
      m = (l + r) // 2
      if self._dfs(reversedGraph, 0, m, set()) == n:
        r = m
      else:
        l = m + 1

    return -1 if l == MAX + 1 else l

  def _dfs(
      self,
      reversedGraph: list[list[tuple]],
      u: int,
      maxWeight: int,
      seen: set[int]
  ) -> int:
    """Returns the number of nodes reachable from u with weight <= maxWeight."""
    res = 1
    seen.add(u)
    for v, w in reversedGraph[u]:
      if w > maxWeight or v in seen:
        continue
      res += self._dfs(reversedGraph, v, maxWeight, seen)
    return res