⚡ Slash the Heaviest Edge & Keep 0 Connected! 🔥 MUST VISIT😎
PLEASE UPVOTE THIS IF U FIND HELPFULL.IntuitionThe problem requires us to modify a directed, weighted graph to meet the following conditions:
Node 0 must be rea
## PLEASE UPVOTE THIS IF U FIND HELPFULL.

## **Intuition**  
The problem requires us to modify a directed, weighted graph to meet the following conditions:  
1. **Node 0 must be reachable from all nodes.**  
2. **Minimize the maximum edge weight used in the final graph.**  
3. **Each node can have at most `k` outgoing edges.**  

To achieve this, we need to **remove** some edges while ensuring that the graph remains connected to node `0`, and we minimize the **maximum edge weight** in the resulting graph.  

### **Key Observations**  
- Since **node 0 must be reachable from all nodes**, we should **reverse the edges** while storing them. Instead of adding edges in the usual `(src → dest)` format, we store them in the **reverse order** `(dest → src)`. This way, we can treat **node 0 as the source** and ensure that all nodes can reach it.  
- We can use **Dijkstra’s algorithm** with a **Min-Heap (PriorityQueue)** to process nodes in increasing order of edge weight, ensuring we get the minimum possible **maximum weight edge** in the final graph.  
- If at the end of traversal, we haven't visited all nodes, it means the graph isn't fully connected, so we return `-1`.

---

## **Approach**  
### **Step 1: Construct the Graph**  
- Create an adjacency list to store edges in a **reverse manner** (`destination → source`).  
- This ensures that while traversing from `0`, we cover all nodes that can **reach** `0`.  

### **Step 2: Use a Priority Queue for Dijkstra’s Algorithm**  
- We maintain a **Min-Heap (PriorityQueue)** that processes nodes in order of **increasing edge weight**.  
- Start with node `0` and traverse the graph using **greedy selection** (always pick the smallest available edge).  

### **Step 3: Keep Track of Maximum Edge Weight**  
- Since we need to **minimize the largest edge weight used**, we keep track of the **maximum edge weight encountered during traversal**.  
- This value will be our final answer.  

### **Step 4: Check if All Nodes Are Visited**  
- If all nodes are reachable from `0`, return the **maximum edge weight** encountered during traversal.  
- Otherwise, return `-1`.  

---

## **Complexity Analysis**  
- **Graph Construction:** \(O(E)\), where `E` is the number of edges.  
- **Sorting (if necessary):** \(O(E \log E)\) (but we are using a min-heap to process edges greedily, which is optimal).  
- **Dijkstra’s Algorithm using a Priority Queue:** \(O(E \log N)\), where `N` is the number of nodes.  
- **Overall Time Complexity:** **\(O(E \log N)\)**  

- **Space Complexity:**  
  - **Graph Representation:** \(O(E)\) (Adjacency List)  
  - **Priority Queue:** \(O(N)\) (At most, all nodes can be in the heap)  
  - **Visited Array:** \(O(N)\)  
  - **Total:** **\(O(N + E)\)**  

---

## **Code**
```java
class Solution {
    public int minMaxWeight(int n, int[][] edges, int k) {
        List<List<int[]>> l=new ArrayList<>();
        for(int i=0;i<n;i++){
            l.add(new ArrayList<>());
        }
        for(int[]e:edges){
            // here we have clue that node 0 will recahable from all other nodes so ab muzhe src to 0 h lena hai to mein ya to normal add krke sort kr skta hu apni list ko ya phir mein ult add krdunga means all nodes will reached by node 0 example1 2,0 hai to isko 2,0 add krne k wjaye 0,2 add krdunga so that mera srck ko dstination mil jaye age bdne k liye.
            l.get(e[1]).add(new int[]{e[0],e[2]});
        }
        PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[1]-b[1]);
        pq.add(new int[]{0,0});
        boolean[]vis=new boolean[n];
        int c=0,max=Integer.MIN_VALUE;
        while(!pq.isEmpty()){
            int[]curr=pq.poll();
            int node=curr[0];
            int val=curr[1];
            if(vis[node])continue;
            vis[node]=true;
            for(int[]neig:l.get(node)){
                pq.add(new int[]{neig[0],neig[1]});
            }
            c++;
            max=Math.max(max,val);
        }
        return (c!=n)?-1:max;
    }
}
```

---

## **Why This Works**
1. **Reversing edges ensures all nodes can reach `0`**  
   - Instead of storing `(src → dest)`, we store `(dest → src)`, making **node 0** the reference point.  
   - This helps in ensuring connectivity from any node to `0`.  

2. **Using a Priority Queue (Min-Heap) ensures we always process the smallest edge weight first**  
   - This **minimizes** the largest edge weight encountered in the final traversal.  

3. **If all nodes are reachable from `0`, we return the largest weight encountered**  
   - This guarantees we meet the problem's constraints.  

4. **If any node is not visited, return `-1`**  
   - This means it’s impossible to satisfy the conditions.

---

## **Example Walkthrough**
### **Input:**
```java
n = 4, edges = [[0,1,4],[1,2,3],[2,3,2],[3,0,5]], k = 2
```
### **Graph Representation After Reversal:**  
```
0 ← 1 (4)  
1 ← 2 (3)  
2 ← 3 (2)  
3 ← 0 (5)
```
### **Priority Queue Processing (Dijkstra's Approach)**
| Step | Node Processed | Edge Weight Used | Max Edge Weight |
|------|--------------|-----------------|-----------------|
| 1    | `0`          | `0`             | `0`             |
| 2    | `3`          | `5`             | `5`             |
| 3    | `2`          | `2`             | `5`             |
| 4    | `1`          | `3`             | `5`             |

### **Final Answer:**  
- All nodes are reachable.  
- The largest edge weight used in the traversal is `5`, so the output is:  
```java
Output: 5
```

---

## **Edge Cases Considered**
✅ **Disconnected Graph:**  
- If any node cannot reach `0`, return `-1`.  

✅ **Threshold Constraints:**  
- Ensures each node has at most `k` outgoing edges (though the pruning part was removed as it's not handled in the current code).  

✅ **Graph with Multiple Paths:**  
- The algorithm always picks the smallest edge first, ensuring the optimal path.

---

## **Final Thoughts**
- This approach ensures that **all nodes remain connected to `0`** while **minimizing the maximum edge weight used**.  
- **Dijkstra’s Algorithm** helps in picking the **minimum possible maximum edge weight** efficiently.  
- The **time complexity of \(O(E \log N)\)** makes it optimal for large graphs. 🚀
['Breadth-First Search', 'Graph', 'Shortest Path', 'Java']