✅Disjoint Set Union, beats 98% | Detailed easy explanation 🚀😊
IntuitionFirst of all, note that AND is a commutative operation, a&b=b&a, and the order of applying AND of edges in a walk does not matter.Also, observe that in
# Intuition
First of all, note that AND is a commutative operation, $a & b = b & a$, and the order of applying AND of edges in a walk does not matter.

Also, observe that in any connected component (subgraph in which every vertex is reachable by other vertex through some path) of the graph, we can have a path that covers all the edges of the component by moving back and forth from every vertex. Eg. when looking for a path from $u$ to $v$, we can go from $u$ to any vertex other than $v$, then go to any other remaning vertex and so on, and lastly reach $v$

Thus a walk exists between any 2 connected nodes, containing atleast all the edges (edges may be repeated in the walk) of that component.

But the trick is, we only need to consider the edges as x & a & a = x & a (applying AND multiple times with same operand has no effect) and AND operation always reduces the value after operation, i.e.
 $a & b <= min(a, b)$

 With these observations, for any connected nodes, the min cost walk is the bitwise AND of all edges in that component. For nodes that are not connected, we can use there is no path, and the answer is -1.

All that remains is to efficiently check for connected components, and computing the total bitwise AND of all edges while adding two nodes connected by an edge. The most intuitive solution that comes to mind is to use a **Disjoint Set Union** data structure aka [DSU](https://cp-algorithms.com/data_structures/disjoint_set_union.html)

# Approach
Use DSU to connect vertices for each edges in $$edges$$. Initialize bitwise AND of component to a large value of form $1111...111$ eg. $2^{30} -1 $ and while combining (union) nodes, compute ANDOfComponent by adding AND of component that is being connected to larger one, and add AND of weight.


# Complexity
- Time complexity:

Complexity of find and union operations is almost constant = $O(\alpha (n))$

Total is $O((m + q)* \alpha(n))$ where $m$ is the number of edges, $n$ is the inverse Ackermann function (it is a slow-growing nearly constant function) 
approximately ~$~O(m + q)$

- Space complexity:
$O(n)$ for DSU, storing $$parent$$, $$rank$$ and $$bitAnd$$ of component

# Code
```cpp []
class Solution {
public:
    class DSU {
        public:

        int n;
        vector<int> parent, rank, bitAnd;
        DSU(int _n) {
            n = _n;
            int maxAnd = pow(2, 30) - 1; // 11111..1111
            parent.resize(n);
            bitAnd.resize(n, maxAnd);
            rank.resize(n, 1); // all components rank 1 initialy
            for (int i = 0; i < n; i++) {
                parent[i] = i; // each is its own parent intiially
            }
        }

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

        // while combining edges, add the bitwise AND of edge to component that becomes parent
        void combine(int x, int y, int w) {
            int rootX = find(x);
            int rootY = find(y);

            if (rootX == rootY) {
                bitAnd[rootX] &= w; // add bitwise AND of edge to component
                return;
            }
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
                bitAnd[rootX] &= bitAnd[rootY];
                bitAnd[rootX] &= w;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
                bitAnd[rootY] &= bitAnd[rootX];
                bitAnd[rootY] &= w;
            } else { // if equal rank, increase rank of the one with more elements
                parent[rootY] = rootX;
                rank[rootX]++;
                bitAnd[rootX] &= bitAnd[rootY];
                bitAnd[rootX] &= w;
            }
        }

        int getANDofComponent(int root) {
            return bitAnd[root];
        }

    };

    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        vector<int> ans;
        DSU dsu = DSU(n);

        for (auto &edge : edges) {
            int ui = edge[0], vi = edge[1], wi = edge[2];
            dsu.combine(ui, vi, wi);
        }

        for (auto &q: query) {
            int ui = q[0], vi = q[1];
            int rootU = dsu.find(ui), rootV = dsu.find(vi);
            if (rootU == rootV) {
                ans.push_back(dsu.getANDofComponent(rootU));
            } else { // diff components, no path exists
                ans.push_back(-1);
            }
        }

        return ans;
    }
};
```
['C++']