Easy Optimized Solution | 2 Approaches | 🥇🥇🥇
IntuitionNode 0 must be reachable from other every nodes. Think of it in reverse way to make it easy. We will start from 0 and try to reach other nodes, while d
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Node 0 must be reachable from other every nodes. Think of it in reverse way to make it easy. We will start from 0 and try to reach other nodes, while doing that its important to visualize that we dont need two edges to reach any other node from 0, if possible. So actually no use of the threshold given.
# Approach 1
<!-- Describe your approach to solving the problem. -->
1. Reverse each edge.
2. Declare a visited array and as INT_MAX;
3. Intialize a min prioriy queue with for {edge_weight, node}. Insert node 0, weight -1 intially.
4. Get one by one from priority queue. If its visited skip. Otherwise, mark visited and store min(ans, weight) in ans, also check for all its adjacent nodes, if not visited then push the weight and adjoint node. Repeat like this untill pq gets empty.
5. At last if any node remains unvisited then return -1. Otherwise return -1.

# Code
```cpp []
class Solution {
public:
    int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {
        vector<vector<pair<int, int>>>adj(n);
        for(auto it : edges){
            int u = it[0];
            int v = it[1];
            int w = it[2];
            adj[v].push_back({w, u});
        }
        vector<int>vis(n, 0);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
        pq.push({-1, 0});
        int maxm = INT_MIN;
        while(!pq.empty()){
            auto it = pq.top();
            pq.pop();
            int node = it.second;
            int w = it.first;
            if(vis[node]) continue;
            maxm = max(maxm, w);
            vis[node] = 1;
            for(auto it : adj[node]){
                if(vis[it.second] == 0){
                    pq.push({it.first, it.second});
                }
            }
        }
        for(auto it : vis) if(it == 0) return -1;
        return maxm;

    }
};
```


# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

$$O(E) + O(V) + O(V*logE) + O(V)$$ => for processing edges, intilize vis vector, priority queue operaion, again loop for vis vector

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(V+E) + O(V) + O(V+E)$$ => for adj list, vis vector, pq




# Approach 2
<!-- Describe your approach to solving the problem. -->
1. Reverse each edge. Intialize ans as -1.
2. Do Binary search from minm edge weight to maxm possible 1e6.
3. Try to do dfs traversal start from 0 to all nodes by allowing maximum edge weight chosen in binary search loop.
4. At the end if all nodes we got visited then try further decreasing the high value to mid - 1 in BS and assign mid to ans, otherwise low = mid + 1. Go untill low <= high.
5. Return ans.

# Code
```cpp []
class Solution {
public:
    int f(int i, int maxm, vector<int>& vis, vector<vector<pair<int, int>>>& adj){
        vis[i] = 1;
        int count = 0;
        for(auto it : adj[i]){
            int w = it.first;
            int node = it.second;
            if(!vis[node] && w <= maxm){
                count += f(node, maxm, vis, adj);
            }
        }
        return count+1;
    }
    int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {
        vector<vector<pair<int, int>>>adj(n);
        for(auto it : edges){
            int u = it[0];
            int v = it[1];
            int w = it[2];
            adj[v].push_back({w, u});
        }
        vector<int>vis(n, 0);
        int low = 1, high = 1e6;
        int ans = -1;
        while(low <= high){
            int mid = low + (high - low)/2;
            vector<int>vis(n, 0);
            if(f(0, mid, vis, adj) == n){
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;

    }
};
```


# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

$$O(E) + O(log(maxm)*(V + E))$$ 

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(V+E) + O(V) + O(V+E)$$ => last V+E for recursion stack



['Binary Search', 'Depth-First Search', 'Graph', 'Heap (Priority Queue)']