What if we reversed everything? 🤔🤔🤔
IntuitionInstead of taking the constraint as: “Node 0 must be reachable from all other nodes”Think of it as: “If we reversed all the edges, Node 0 must be able
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Instead of taking the constraint as: “Node 0 must be reachable from all other nodes”

Think of it as: “If we reversed all the edges, Node 0 must be able to reach all other nodes” 


# Approach
<!-- Describe your approach to solving the problem. -->
Reverse all the edges


Given a certain maximum edge weight, we can filter out the edges with weight greater than this max and do a dfs/bfs on the graph to see if the remaining edges satisfy the new condition we defined


But what about the threshold?


This condition actually doesn’t matter because if it is at all possible for node 0 to be reachable from every other node, then simply picking exactly one edge per node is enough to maintain connectivity


# Code
```
class Solution {
    public int minMaxWeight(int n, int[][] edges, int threshold) {        
        List<List<Integer>> rev = new ArrayList<>(n);
        for(int i = 0; i < n; i++) {
            rev.add(new ArrayList<>());
        }
        
        Set<Integer> weightSet = new HashSet<>();
        for(int[] e : edges) {
            int u = e[0], v = e[1];
            int w = e[2];
            rev.get(v).add(u);
            weightSet.add(w);
        }
        
        if(!can(n, rev)) {
            return -1;
        }
        
        List<Integer> weights = new ArrayList<>(weightSet);
        Collections.sort(weights);
        
        int left = 0;
        int right = weights.size() - 1;
        int ans = -1;
        
        while(left <= right) {
            int mid = (left + right) / 2;
            int W = weights.get(mid);
            
            List<List<Integer>> temp = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                temp.add(new ArrayList<>());
            }
            for (int[] e : edges) {
                int u = e[0], v = e[1], w = e[2];
                if (w <= W) {
                    temp.get(v).add(u);
                }
            }
            
            if(canVisitAll(n, temp)) {
                ans = W;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return ans;
    }
    
    public boolean canVisitAll(int n, List<List<Integer>> revGraph) {
        boolean[] visited = new boolean[n];
        visited[0] = true;
        int count = 1;
        
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(0);
        
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            for(int nxt : revGraph.get(cur)) {
                if(!visited[nxt]) {
                    visited[nxt] = true;
                    count++;
                    queue.offer(nxt);
                }
            }
        }
        
        return count == n;
    }
    
    public boolean can(int n, List<List<Integer>> rev) {
        boolean[] visited = new boolean[n];
        visited[0] = true;
        int count = 1;
        
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(0);
        
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            for(int nxt : rev.get(cur)) {
                if(!visited[nxt]) {
                    visited[nxt] = true;
                    count++;
                    queue.offer(nxt);
                }
            }
        }
        return count == n;
    }
}
```

['Java']