LC 3419. Minimize the Maximum Edge Weight of Graph

https://leetcode.com/problems/minimize-the-maximum-edge-weight-of-graph/description/

Tag: Binary Search, DFS

class Solution {
public:
    void dfs(int pre, int cur, vector<vector<pair<int, int>>> &g, vector<bool> &vis, int target) {
        vis[cur] = true;
        for (auto &[nxt, val]: g[cur]) {
            if (nxt == pre || val > target || vis[nxt]) continue;
            dfs(cur, nxt, g, vis, target);
        }
    }

    int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {
        vector<vector<pair<int, int>>> g(n);
        for (auto &x: edges) {
            g[x[1]].push_back({x[0], x[2]});
        }
        int l = 1, r = 1e6 + 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            vector<bool> vis(n, false);
            dfs(-1, 0, g, vis, mid);
            int cnt = 0;
            for (int i = 0; i < n; i++) cnt += vis[i];
            if (cnt == n) r = mid;
            else l = mid + 1;
        }
        return l == 1e6 + 1 ? -1 : l;
    }
};

本題只有一個大陷阱就是那個沒用的 threshold，只要把他當空氣很快就可以解出來了。