DSU | C++ | Intuitive Approach | Clean Solution | Graph
IntuitionThe problem requires us to find the minimum cost of a walk between two nodes in an undirected weighted graph, where the cost is defined as the bitwise


### **Intuition**  
The problem requires us to find the minimum cost of a walk between two nodes in an undirected weighted graph, where the cost is defined as the bitwise AND of all edge weights encountered.  

A key observation is that the bitwise AND operation is **monotonically non-increasing**—meaning that as we take the AND of more numbers, the result either **decreases or remains the same**. This implies that for any connected component, the minimum possible cost for a walk between any two nodes in that component is simply the **AND of all edge weights within the component**.  

To efficiently track connected components and their associated AND values, we use a **Union-Find (Disjoint Set Union, DSU)** data structure. This allows us to efficiently merge components and track their bitwise AND values while processing edges.  

---

### **Approach**  
1. **Initialize DSU**:  
   - Create a `parent` array where each node is initially its own parent.
   - Create a `cost` array where each node initially has a cost of `-1`.

2. **Processing Edges**:  
   - For each edge `(u, v, wt)`, find the parent of `u` and `v`.
   - If `u` and `v` belong to different components, merge them using the Union-Find structure.
   - As we merge components, update the `cost` array to maintain the bitwise **AND of all edge weights** in the component.
   - Since AND is **monotonically non-increasing**, the cost for each component will either **decrease or stay the same** as more edges are merged.

3. **Processing Queries**:  
   - For each query `(s, t)`, find the representative (parent) of both nodes.
   - If `s` and `t` belong to the same connected component, return the stored **AND value** for that component.
   - Otherwise, return `-1` (no path exists between them).

---

### **Complexity Analysis**  
- **Time Complexity**:  
  - Union-Find operations run in nearly **O(1)** time due to path compression.
  - Processing `m` edges takes **O(m α(n))**, where `α(n)` is the inverse Ackermann function.
  - Processing `q` queries takes **O(q α(n))**.
  - Overall complexity: **O((m + q) α(n))**, which is nearly linear.

- **Space Complexity**:  
  - **O(n)** for the parent array.
  - **O(n)** for the cost array.
  - **O(m + q)** for storing edges and queries.
  - Overall: **O(n + m + q)**.



# Code
```cpp []
class Solution {
    vector<int> parent;
    int find(int x)
    {
        if(parent[x] == x)
            return x;

        return parent[x] = find(parent[x]);
    }

    void Union(int u, int v)
    {
        parent[v] = u;
    }
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges,
                            vector<vector<int>>& query) {
        parent.resize(n);
        vector<int> cost(n, -1);
        for(int i=0; i<n; i++)
        {
            parent[i] = i;
        }

        for(auto e:edges)
        {
            int u = e[0];
            int v = e[1];
            int wt = e[2];

            int par_u = find(u);
            int par_v = find(v);

            if(par_u != par_v)
            {
                Union(par_u, par_v);

                cost[par_u] &=  cost[par_v];
            }
            cost[par_u] &= wt;
        }

        vector<int> res;

        for(auto q:query)
        {
            int s = q[0];
            int t = q[1];

            int par_s = find(s);
            int par_t = find(t);

            if(par_s == par_t)
                res.push_back(cost[par_s]);
            else
                res.push_back(-1);
        }

        return res;
    }
};
```
['Union Find', 'Graph', 'C++']