Use Disjoint Set Union (DSU) to Find Connected Components || C++ || Java || 100 % Beats ||
Intuition
We are given an undirected weighted graph, where each edge has a weight.
A walk can traverse edges and nodes multiple times.
The cost of a walk is the
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
- We are given an undirected weighted graph, where each edge has a weight.
- A walk can traverse edges and nodes multiple times.
- The cost of a walk is the bitwise AND of all edge weights traversed.
- The goal is to find the minimum cost walk from si to ti for each query.

# Approach
<!-- Describe your approach to solving the problem. -->
1. **Use Disjoi****nt Set U****nion (DSU) to Find Connected Components**
- First, we find all connected components using the DSU (Union-Find) data structure.
- If two nodes are in different components, the answer is -1.
2. **Build Graph Representation**
- We use an adjacency list to store the graph as an unordered_map<int, vector<pair<int, int>>> (where pair<int, int> represents (neighbor, weight)).
3. **Precompute Minimum AND-Cost for Each Component**
- For each connected component, we use **BFS** to compute the **minimum AND cost** of all paths within that component.
- We traverse the component, computing the **bitwise AND of all edge weights.**
4. **Answer Queries in O(1)**
- Once preprocessed, each query can be answered in **constant time** using DSU.


# Complexity
1. Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
- Graph Construction:O(E)
- **DSU Operations** (Union + Path Compression): O(α(N)), which is nearly **constant**.
- Precomputing **AND Costs** (BFS for each component): O(N+E)
- Query Answering: O(1) per query
- Total Complexity:O(N+E+Q)
This is optimal given the constraints.

2. Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
- Graph Storage: O(N+E)
- DSU Parent & Rank Arrays: O(N)
- Visited and Cost Arrays: O(N)
- Total Space Complexity:O(N+E)

# Code
```cpp []
class DSU {
public:
    vector<int> parent, rank;
    
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 1);
        iota(parent.begin(), parent.end(), 0);
    }
    
    int find(int x) {
        if (parent[x] != x) 
            parent[x] = find(parent[x]); // Path compression
        return parent[x];
    }
    
    void unite(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) swap(rootX, rootY);
            parent[rootX] = rootY;
            if (rank[rootX] == rank[rootY]) rank[rootY]++;
        }
    }
};


class Solution {
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        DSU dsu(n);
        
        // Step 2: Merge nodes that are directly connected
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            dsu.unite(u, v);
        }
        
        // Step 3: Check if nodes are in the same connected component
        unordered_map<int, vector<pair<int, int>>> graph;
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }

        // Step 4: Precompute the minimum AND-cost for each connected component
        vector<int> minCost(n, INT_MAX);
        for (int i = 0; i < n; i++) {
            if (dsu.find(i) == i) {
                queue<int> q;
                unordered_set<int> visited;
                q.push(i);
                visited.insert(i);
                int andCost = INT_MAX;

                while (!q.empty()) {
                    int node = q.front(); q.pop();
                    for (auto [neighbor, weight] : graph[node]) {
                        andCost &= weight;
                        if (!visited.count(neighbor)) {
                            q.push(neighbor);
                            visited.insert(neighbor);
                        }
                    }
                }
                minCost[i] = andCost;
            }
        }

        // Step 5: Answer queries in O(1)
        vector<int> result;
        for (auto& q : query) {
            int u = q[0], v = q[1];
            if (dsu.find(u) != dsu.find(v)) {
                result.push_back(-1);
            } else {
                result.push_back(minCost[dsu.find(u)]);
            }
        }
        return result;
    }
};
```
['C++']