DFS|UnionFind with size/rank+ bit_and||C++ 6ms Beats 99.35%
Intuition
Key Observation: It's  good  to know that every path in the same  connected component has the the same cost, due to that every  vertex can be  revisit
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
1. *Key Observation*: **It's  good  to know that every path in the same  connected component has the the same cost**, due to that every  vertex can be  revisited in an arbitrary number of times.
2. Use UnionFind class with size/rank to optimize.
Once the implementation for UnionFind class is done, the problem is not far from solving.
3. Since among different vertices there may exist multiple edges with different weights, the DFS is doable but not conventional, instead of marking the visited vertices but to mark the visited edges. The speed is slow, but accepted & for fun.
# Approach
<!-- Describe your approach to solving the problem. -->
UnionFind makes some quesitions easier
the Union Find class with members `root`, `Size`, `Find`, `Union`, `connected`! The very crucial fact is that **every vertex in a connected component shares a common root, i.e. x is connected to y** $\iff$ Find(x)==Find(y) $\iff$ root[x]==root[y] $\iff$ connected(x, y)==true

Some problems are good to solve by using UnionFind

[1971. Find if Path Exists in Graph](https://leetcode.com/problems/find-if-path-exists-in-graph/solutions/5052126/union-find-is-good-vs-dfs-vs-bfs-193ms-beats-99-93)
[2658. Maximum Number of Fish in a Grid](https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/solutions/6337415/ez-dfsc-beats-100-by-anwendeng-nd07/)
[684. Redundant Connection](https://leetcode.com/problems/redundant-connection/solutions/6341974/unionfind-is-goodbeats-100-by-anwendeng-nhlh/)
[827. Making A Large Island](https://leetcode.com/problems/making-a-large-island/solutions/6350236/unionfind-with-size-member-vs-dfs-vs-bfs-39ms-beats-99-53/)
[959. Regions Cut By Slashes](https://leetcode.com/problems/regions-cut-by-slashes/solutions/5614770/unionfind-dfs-euler-theorem-v-e-f-2-beats-100/)

[LC 959. Please turn English subtitles if necessary]
[https://youtu.be/cR_D4uA3g3s?si=pRUu-8zRIMmCJHM2](https://youtu.be/cR_D4uA3g3s?si=pRUu-8zRIMmCJHM2)
# UnionFind with Size used in this solution
```cpp [ vector ver]
// union find class with size
class UnionFind {
public:
    vector<int> root, Size; // Size is public easy for using
    UnionFind(int N): root(N), Size(N, 1){
        iota(root.begin(), root.end(), 0);    
    }
    
    int Find(int x) {
        return (x==root[x]) ? x : root[x] = Find(root[x]);
    }

    bool Union(int x, int y) {       
        x=Find(x), y=Find(y);
        if (x == y) return 0; //already have same root
        if (Size[x] > Size[y]) {
            Size[x] +=Size[y];
            root[y] = x;
        } 
        else {
            Size[y] += Size[x];
            root[x] = y;
        }       
        return 1;// merge 2 disjoint sets
    } 
    bool connected(int x, int y) {
        return Find(x) == Find(y);
    }
};
```
```cpp [C array ver]
class UnionFind {
public:
    int root[100000], Size[100000];
    UnionFind(int N){
        iota(root, root+N, 0);
        fill(Size, Size+N, 1);    
    }
    
    int Find(int x) {
        return (x==root[x]) ? x : root[x] = Find(root[x]);
    }

    bool Union(int x, int y) {       
        x=Find(x), y=Find(y);
        if (x == y) return 0; //already have same root
        if (Size[x] > Size[y]) {
            Size[x] +=Size[y];
            root[y] = x;
        } 
        else {
            Size[y] += Size[x];
            root[x] = y;
        }       
        return 1;// merge 2 disjoint sets
    } 
    bool connected(int x, int y) {
        return Find(x) == Find(y);
    }
};
```
# UnionFind class with rank optimization which is more popular
```
class UnionFind {
public:
    int root[100000], rank[100000];
    UnionFind(int N){
        iota(root, root+N, 0);
        fill(rank, rank+N, 1);    
    }
    
    int Find(int x) {
        return (x==root[x]) ? x : root[x] = Find(root[x]);
    }

    void Union(int x, int y) {//Union by rank
        int rX = Find(x), rY = Find(y);
        if (rX == rY)
            return;
        if (rank[rX] > rank[rY])
            swap(rX, rY);
        root[rX] = rY;
        if (rank[rX] == rank[rY])
            rank[rY]++;
    }
    bool connected(int x, int y) {
        return Find(x) == Find(y);
    }
};
```
[LC1971 uses this UnionFind class with rank. Please turn English subtitles if necessary]
[https://youtu.be/B1GQlUN08lk?si=DpfxrPBWc-t5eSPi](https://youtu.be/B1GQlUN08lk?si=DpfxrPBWc-t5eSPi)
In the function `minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query)` :
1. Create UnionFind object `graph(n)`
2. let the vector `cost(n, UINT_MAX)` be initialized with all bits being set
3. For every `vec=(u, v, w)` in `edges` to proceed
```
int wt=cost[graph.Find(u)] & cost[graph.Find(v)] & w;// set wt
graph.Union(u, v);// unify  u & v
int rt=graph.Find(u); // find the new root for u
cost[rt]&=wt; // update cost[rt]
```
4. let `m=|query|` & initialize `ans(m, -1)`
5. Proceed the loop for `(s, t)=queriy[i]`
```
if (graph.connected(s, t))
    ans[i]=cost[graph.Find(s)];
```
6. return `ans`
7. Python code is made.
8. The benefit for using UnionFind is no need for constructing the adjacent lists  contray to DFS or BFS method which is sometimes very time consuming.
5. But UnionFind class with rank is maybe a better choice for this problem which has the elapsed  time 6ms
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(n+(E+m)\alpha (n))$ where $E=|edges|$, $\alpha(\cdot)$ is the inverse Ackermann function which grows very slowly
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(n)$
# Code|UnionFind with Size using vector version 11ms|UnionFind with Size using C array ver 10ms Beats 94.48%|UnionFind class with rank 6ms Beats 99.35%
```cpp []
class Solution {
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) 
    {
        UnionFind graph(n);
        vector<unsigned> cost(n, UINT_MAX);
        for (auto& vec: edges){
            int u=vec[0], v=vec[1], w=vec[2];
            int wt=cost[graph.Find(u)] & cost[graph.Find(v)] & w;
            graph.Union(u, v);
            int rt=graph.Find(u);
            cost[rt]&=wt;
        }
        int m=query.size();
        vector<int> ans(m, -1);
        for(int i=0; i<m; i++){
            int s=query[i][0], t=query[i][1];
            if (graph.connected(s, t))
                ans[i]=cost[graph.Find(s)];
        }
        return ans;
    }
};

auto init = []()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
}();
```
# Python code is slow but accepted
```
class UnionFind:
    def __init__(self, N):
        self.root = list(range(N))
        self.Size = [1]*N

    def Find(self, x):
        if self.root[x] != x:
            self.root[x] = self.Find(self.root[x])  # path compression
        return self.root[x]

    def Union(self, x, y):
        x = self.Find(x)
        y = self.Find(y)
        if x==y: return False

        if self.Size[x] > self.Size[y]:
            self.Size[x] += self.Size[y]
            self.root[y]=x
        else:
            self.Size[y] += self.Size[x]
            self.root[x]=y
        return True
class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        graph=UnionFind(n)
        cost=[0xFFFFFFFF]*n
        for u, v, w in edges:
            wt=cost[graph.Find(u)] & cost[graph.Find(v)] & w
            graph.Union(u, v)
            rt=graph.Find(u)
            cost[rt]&=wt
        ans=[-1]*(len(query))
        for i, (s, t) in enumerate(query):
            rootS=graph.Find(s)
            if rootS==graph.Find(t):
                ans[i]=cost[rootS]
        return ans
        
```
# unconventional DFS
```
class Solution {
public:
    using int3=tuple<int, int, int>;//(v, weight, edge id)
    const static int N=100000;
    vector<int3> adj[N];
    int root[N], cost[N];
    bitset<N> Evis;

    void dfs(int rt, int i, int wt) {
        root[i]=rt;
        cost[rt]&=wt;  // Update cost

        for (auto& [j, w, eIdx] : adj[i]) {
            if (Evis[eIdx]) continue;
            Evis[eIdx]=1;
            dfs(rt, j, wt&w);
        }
    }

    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        memset(root, -1, sizeof(int)*n);
        memset(cost, -1, sizeof(int)*n);

        int E=edges.size();
        for (int i=0; i<E; i++) {
            const int u=edges[i][0], v=edges[i][1], w=edges[i][2];
            adj[u].emplace_back(v, w, i);
            adj[v].emplace_back(u, w, i);
        }

        for (int i = 0; i<n; i++) {
            if (root[i]==-1) 
                dfs(i, i, -1);
        }
        int m=query.size();
        vector<int> ans(m, -1);
        for (int i = 0; i < m; i++) {
            int s=query[i][0], t=query[i][1];
            if (root[s] == root[t]) 
                ans[i] = cost[root[s]];
        }
        return ans;
    }
};

```
['Bit Manipulation', 'Depth-First Search', 'Union Find', 'Graph', 'C++', 'Python3']