Minium Cost Walk Optimized Solution
IntuitionThe goal is to find the minimum cost of a walk between two nodes in a weighted undirected graph using bitwise AND of edge weights. Since a walk can vis
# Intuition
The goal is to find the minimum cost of a walk between two nodes in a weighted undirected graph using bitwise AND of edge weights. Since a walk can visit nodes and edges multiple times, we mainly need to check connectivity.

- Connectivity Check: First, we check if two nodes belong to the same connected component using Union-Find (Disjoint Set Union - DSU).
- Minimum Cost Calculation: For each connected component, compute the bitwise AND of all edge weights within that component.
- Answer Queries: For each query, if both nodes are connected, return the precomputed AND cost; otherwise, return -1.

# Approach
1. Union-Find Initialization:
     - Initialize parent and rank for Union-Find to manage connected components.
2. Perform Union Operations:
    - For each edge, union the two connected nodes.
3. Compute Minimum AND Cost:
    - Track the bitwise AND of all edge weights within each connected component using a cc array.
4. Process Queries:
    - Check if both nodes in the query belong to the same component using the find() function.
    - If connected, return the component’s AND value; otherwise, return -1.

# Complexity
- Time complexity:
    - Union-Find operations are nearly constant with path compression and union by rank: O(α(N)).
    - Edge processing takes O(E).
    - Queries take O(Q) for connectivity checks.
    - Overall: O(N + E + Q).

- Space complexity:
    - O(N + E + Q) for storing parent, rank, connected component values, and results.

# Code
```java []
class Solution {
    int[] par;
    int[] depth;
    public int find(int root){
        if(par[root]==-1) return root;
        return par[root] = find(par[root]);
    }
    public void union(int node1,int node2){
        int root1 = find(node1);
        int root2  = find(node2);
        if(root1==root2) return;
        if(depth[root1]<depth[root2]){
            int temp = root1;
            root1 = root2;
            root2  = temp;
        }
        par[root2] = root1;
        if(depth[root1]==depth[root2]){
            depth[root1]++;
        }
    }
    public int[] minimumCost(int n, int[][] edges, int[][] query) {
        par = new int[n];
        Arrays.fill(par,-1);
        depth = new int[n];
        int[] cc = new int[n];
        Arrays.fill(cc,Integer.MAX_VALUE);
        for(int[] edge : edges){
            union(edge[0],edge[1]);
        }
        for(int[] edge : edges){
            int root = find(edge[0]);
            cc[root]&=edge[2];
        }
        int[] res = new int[query.length];
        for(int i = 0;i<query.length;i++){
            int s = query[i][0];
            int e  = query[i][1];
            if(find(s)!=find(e)){
                res[i] = -1;
                continue;
            }
            int root = find(s);
            res[i] = cc[root];
        }
        return res;
    }
}
```
```  Python []
class Solution:
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

    def minimumCost(self, n, edges, query):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
        cc = [(2**31 - 1)] * n 
        for u, v, w in edges:
            self.union(u, v)
        for u, v, w in edges:
            root = self.find(u)
            cc[root] &= w
        res = []
        for s, t in query:
            if self.find(s) != self.find(t):
                res.append(-1)
            else:
                res.append(cc[self.find(s)])
        return res
```
```C++ []
class Solution {
public:
    vector<int> parent, rank, cc;

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unionNodes(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        parent.resize(n);
        rank.resize(n, 0);
        cc.resize(n, INT_MAX);

        iota(parent.begin(), parent.end(), 0);

        for (auto& e : edges) {
            unionNodes(e[0], e[1]);
        }

        for (auto& e : edges) {
            int root = find(e[0]);
            cc[root] &= e[2];
        }

        vector<int> res;
        for (auto& q : query) {
            if (find(q[0]) != find(q[1])) {
                res.push_back(-1);
            } else {
                res.push_back(cc[find(q[0])]);
            }
        }
        return res;
    }
};
```
```Javascript []
/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number[][]} query
 * @return {number[]}
 */
var minimumCost = function(n, edges, query) {
    const parent = Array.from({ length: n }, (_, i) => i);
    const rank = Array(n).fill(0);
    const cc = Array(n).fill(0x7FFFFFFF); 
    const find = (x) => {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    };
    const union = (x, y) => {
        const rootX = find(x);
        const rootY = find(y);
        if (rootX !== rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    };
    for (const [u, v, w] of edges) {
        union(u, v);
    }
    for (const [u, v, w] of edges) {
        const root = find(u);
        cc[root] &= w;
    }
    const result = [];
    for (const [s, t] of query) {
        if (find(s) !== find(t)) {
            result.push(-1);
        } else {
            result.push(cc[find(s)]);
        }
    }

    return result;
};
```
['Bit Manipulation', 'Graph', 'Python', 'C++', 'Java', 'JavaScript']