"Reverse Graph + Priority Queue | 100% Time Complexity Beat | 92% Space Complexity Beat
IntuitionIntuition is similar to prim's algorithm for minimum spanning tree,  reverse the given directed edges so that the question becomes there should be a pa
# **Intuition**  
Intuition is similar to prim's algorithm for minimum spanning tree,  reverse the given directed edges so that the question becomes there should be a path from node 0 to every other node , also the outgoing threshold given in question becomes incoming threshold

---

# **Approach**  
1. Reverse the edges to convert the problem into checking paths from node `0`.
2. Use an adjacency list to represent the reversed graph.
3. Implement a modified Prim's algorithm using a priority queue:
   - Push edges in increasing order of weight.
   - Track node visits and degrees to ensure threshold constraints.
   - Update the maximum edge weight (`ans`) during traversal.
4. If any node is unreachable, return `-1`. Otherwise, return `ans`.

---

# **Complexity**  
- **Time Complexity**:  
  The time complexity is $$O((m + n) \log n)$$, where:  
  - $$m$$ is the number of edges, and $$n$$ is the number of nodes.  
  - Traversing the adjacency list takes $$O(m)$$.  
  - Priority queue operations (insertion and extraction) take $$O(\log n)$$ for each of the $$n$$ nodes.

- **Space Complexity**:  
  The space complexity is $$O(m + n)$$, as we store the adjacency list, visited array, and degree array.

---

# Code
```cpp []
class Solution {
public:
    int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {
        
        // let's try prims , long time no see
        vector<vector< pair<int , int> > > adj(n);
        int m = edges.size();
        for(int i = 0 ; i < m ; i++){
        //    adj[edges[i][0]].push_back({edges[i][1] , edges[i][2]});
           adj[edges[i][1]].push_back({edges[i][0] , edges[i][2]});
        }

        vector<int> deg(n , 0);
        vector<int> vis(n , 0);

        int ans = 0;

        priority_queue< pair<int , int> , vector< pair<int , int> > , greater< pair<int , int> > > pq;
        pq.push({0 , 0});

        while(!pq.empty()){
            auto it = pq.top();
            pq.pop();

            int node = it.second;
            int edgewt = it.first;

            if(vis[node])continue;

            if(deg[node] < threshold){
                deg[node]++;
                ans = max(ans , edgewt);
                vis[node] = 1;
            }
            else continue;

            for(auto [adjnode , wt] : adj[node]){
                if(vis[adjnode] == 0)
                pq.push({wt ,adjnode });
            }
        }

        for(int i = 0 ; i < n ; i++){
            if(vis[i] == 0){
                return -1;
            }
        }

        return ans;
    }
};
```
['Heap (Priority Queue)', 'Minimum Spanning Tree', 'C++']