✅ Easy to Understand | Disjoint Set Union | Detailed Video Explanation🔥
IntuitionThe problem requires finding the minimum cost walk between two nodes in a weighted graph. Observing the constraints, we can leverage the Disjoint Set U
# Intuition
The problem requires finding the minimum cost walk between two nodes in a weighted graph. Observing the constraints, we can leverage the **Disjoint Set Union (DSU)** to group connected components and determine the minimum possible cost within each component. By storing the bitwise AND of all edge weights in a connected component, we can efficiently answer queries about whether two nodes are connected and their associated minimum cost.

# Approach
1. **Initialize DSU**: Use the Disjoint Set Union (DSU) to track connected components.
2. **Build Connected Components**: Iterate through the edges and unite the connected nodes.
3. **Compute Component Costs**: For each component, compute the bitwise AND of all edge weights to determine the minimum cost within that component.
4. **Answer Queries**: For each query:
   - If the two nodes belong to different components, return `-1`.
   - Otherwise, return the precomputed cost of their component.

This approach efficiently determines connectivity and minimum cost using **DSU with path compression**, ensuring optimal performance.

# Complexity
- **Time Complexity**:  
  - **Union-Find Operations**: Each `find` and `union` operation runs in nearly constant time using path compression, i.e., $$O(E \alpha(N))$$.
  - **Component Cost Calculation**: Iterates through the edges, $$O(E)$$.
  - **Query Processing**: Each query takes $$O(\alpha(N))$$, leading to $$O(M \alpha(N))$$.
  - **Overall Complexity**: $$O(E + M)$$.

- **Space Complexity**:  
  - **Parent Array**: $$O(N)$$.
  - **Component Cost Array**: $$O(N)$$.
  - **Result Storage**: $$O(M)$$.
  - **Overall Complexity**: $$O(N + M)$$.


# Code
```java []
class Solution {
    int[] parent;

    public int find (int x){
        if(parent[x] == -1) return x;
        return parent[x] = find(parent[x]); // path compression , pruning. 
    }
    public void union(int a, int b){
        int pa = find(a);
        int pb = find(b);
        if(pa != pb){
            parent[pb] = pa;
        }
    }
    // O(E + M) , m number of qureis. 
    public int[] minimumCost(int n, int[][] edges, int[][] query) {
        // dsu
        parent = new int[n];
        Arrays.fill(parent, -1);

        for(int[] edge : edges){
            union(edge[0], edge[1]);
        }

        // parent -> cost ( & of all weights in that connected component ). 
        int[] componentCost = new int[n];
        Arrays.fill(componentCost, Integer.MAX_VALUE);

        for(int[] edge : edges){
            // u -> v
            int parent = find(edge[0]);
            componentCost[parent] &= edge[2];
        }      

        // [start, end]  pstart, pend & 
        int[] ans = new int[query.length]; int i=0;
        for(int[] q: query){
            int ps = find(q[0]);
            int pe = find(q[1]);
            if(ps != pe) 
                ans[i] = -1;
            else{
                ans[i] = componentCost[ps];
            }
            i++;        
        }
        return ans;
    }
}


```

https://youtu.be/Xd_AVgytJns


['Array', 'Union Find', 'Graph', 'Java']