Java | Optimized DSU with Path Compression | 99.86% Beats 🔥| O(E + Q)
IntuitionThe problem requires us to find the minimum cost walk between two nodes in an undirected weighted graph. The cost of a walk is defined as the bitwise A
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires us to find the minimum cost walk between two nodes in an undirected weighted graph. The cost of a walk is defined as the bitwise AND of all edge weights along the path.

To solve this efficiently, we can observe that:

If two nodes are not connected, the answer is -1.
If two nodes are connected, the minimum AND-value of all edges in that connected component gives the answer.
Since the graph is undirected, nodes that are connected form components.
Thus, we can use Disjoint Set Union (DSU) / Union-Find to efficiently group connected nodes and track the minimum AND-value for each component.

# Approach
<!-- Describe your approach to solving the problem. -->
1️⃣ Use Union-Find to Build Components
We initialize the DSU structure (parent, rank, minAnd).
Each node starts as its own parent (parent[node] = -1).
The minAnd array stores the minimum AND-value for each component (initialized to Integer.MAX_VALUE).
We process each edge (u, v, w):
Merge u and v into the same component.
Update the minAnd value to track the smallest possible AND value within the component.

2️⃣ Answer Queries in O(1)
For each query (si, ti):
If find(si) != find(ti), they are in different components, so return -1.
Otherwise, return minAnd[find(si)], which gives the minimum cost of any walk in the same component.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
for find(u) func -> O(α(V)) (almost constant due to path compression)
for union(u, v) func -> O(α(V))
Processing all E edges: O(E * α(V))
Processing all Q queries: O(Q * α(V))
Overall: O((E + Q) * α(V)) ≈ O(E + Q), since α(V) ≈ O(1)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
parent, rank, and minAnd arrays: O(V)
Total: O(V)
# Code
```java []
class Solution {
    int[] parent,rank,minAnd;

    public int find(int node){
        if(parent[node] == -1)  return node;
        return parent[node] = find(parent[node]);
    }

    public void union(int u,int v,int w){
        int rootU = find(u);
        int rootV = find(v);

        if(rootU == rootV){
            minAnd[rootU] &= w;
            return;
        }

        if(rank[rootU] < rank[rootV]){
            parent[rootU] = rootV;
            minAnd[rootV] &= (minAnd[rootU] & w);
        }
        else if(rank[rootU] > rank[rootV]){
            parent[rootV] = rootU;
            minAnd[rootU] &= (minAnd[rootV] & w);
        }
        else{
            parent[rootU] = rootV;
            rank[rootV]++;
            minAnd[rootV] &= (minAnd[rootU] & w);
            // It can be done for rootV also, since absolute 
            //roots of both rootU & rootV are equal, we can 
            //do both ways
        }
    }

    public int[] minimumCost(int n, int[][] edges, int[][] query) {
        parent = new int[n];
        rank = new int[n];
        minAnd = new int[n];

        Arrays.fill(parent,-1);
        Arrays.fill(rank,0);
        Arrays.fill(minAnd,Integer.MAX_VALUE);

        // 1. Build graph
        for(int[] edge : edges){

            int u = edge[0], v = edge[1], w = edge[2];
            union(u,v,w);
        }

        // 2. Get cost
        int[] res = new int[query.length];
        for(int i=0; i<query.length; i++){
            
            int u = query[i][0], v = query[i][1];

            if(find(u) != find(v))  res[i] = -1;
            else  res[i] = minAnd[find(u)]; 
        }
        return res;
    }
}
```
['Java']