🚀 Union Find | ✅With Hints | Short & Clear Explanation | C++ | Python | Java | Go
😊 Kindly try to solve it yourself first
  Hint 1.
  Try using DSU (Disjoin Set Union) to group nodes together based on connectivity.

  Hint 2.
  Use the bitwis
## 😊 Kindly try to solve it yourself first
<details>
  <summary><span style="font-size:20px;">Hint 1.</span></summary>
  <span style="font-size:16px;">Try using <strong>DSU (Disjoin Set Union)</strong> to group nodes together based on connectivity.</span>
</details>
<br>
<details>
  <summary><span style="font-size:20px;">Hint 2.</span></summary>
  <span style="font-size:16px;">Use the bitwise <strong>AND</strong> operation to <strong>merge cost values of two connected components</strong>. This ensures that only common set bits remain.</span>
</details>
<br>
<details>
  <summary><span style="font-size:20px;">Hint 3.</span></summary>
  <span style="font-size:16px;">For each query, if <strong>both nodes belong to the same component</strong>, output the merged cost. Otherwise, the answer is <strong>-1</strong>.</span>
</details>
<br>
<details>
  <summary><span style="font-size:20px;">Hint 4.</span></summary>
  <span style="font-size:16px;">Build a Union-Find structure where each node starts with its cost. For every edge, <strong>merge the sets</strong> using union-find and update the cost with bitwise <strong>AND</strong>. Then for each query, if the two nodes have the <strong>same representative</strong>, return the component’s cost; else , return -1.</span>
</details>

---

# 🚀 Approach
- We use **Union-Find (Disjoint Set)** to efficiently merge nodes based on edges.
- Each connected component maintains a **minimum cost** value using bitwise **AND**.
- For each query:
  - If `q[0] == q[1]`, return `0` since it's the same node.
  - If they belong to **different components**, return `-1`.
  - Otherwise, return the **minimum cost** of their component.

---

# 🧩 Implementation
```cpp []
class Solution {
public:
    vector<int> parent, minCost;

    int find(int node) {
        return parent[node] < 0 ? node : parent[node] = find(parent[node]);
    }

    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        parent = minCost = vector<int>(n, -1);

        for (auto &edge : edges) {
            int uRoot = find(edge[0]), vRoot = find(edge[1]);
            if (uRoot != vRoot) {
                minCost[uRoot] &= minCost[vRoot];
                parent[vRoot] = uRoot;
            }
            minCost[uRoot] &= edge[2];
        }

        vector<int> result;
        for (auto &q : query) {
            int uRoot = find(q[0]), vRoot = find(q[1]);
            if (q[0] == q[1]) result.push_back(0);
            else if (uRoot != vRoot) result.push_back(-1);
            else result.push_back(minCost[uRoot]);
        }

        return result;
    }
};
```
```Python []
class Solution:
    def find(self, node, parent):
        if parent[node] < 0:
            return node
        parent[node] = self.find(parent[node], parent)
        return parent[node]

    def minimumCost(self, n: int, edges: list[list[int]], query: list[list[int]]) -> list[int]:
        parent = [-1] * n
        minCost = [-1] * n

        for u, v, cost in edges:
            uRoot, vRoot = self.find(u, parent), self.find(v, parent)
            if uRoot != vRoot:
                minCost[uRoot] &= minCost[vRoot]
                parent[vRoot] = uRoot
            minCost[uRoot] &= cost

        result = []
        for u, v in query:
            uRoot, vRoot = self.find(u, parent), self.find(v, parent)
            if u == v:
                result.append(0)
            elif uRoot != vRoot:
                result.append(-1)
            else:
                result.append(minCost[uRoot])

        return result
```
```Java []
class Solution {
    int[] parent, minCost;

    private int find(int node) {
        if (parent[node] < 0) return node;
        return parent[node] = find(parent[node]);
    }

    public int[] minimumCost(int n, int[][] edges, int[][] query) {
        parent = new int[n];
        minCost = new int[n];
        Arrays.fill(parent, -1);
        Arrays.fill(minCost, -1);

        for (int[] edge : edges) {
            int uRoot = find(edge[0]), vRoot = find(edge[1]);
            if (uRoot != vRoot) {
                minCost[uRoot] &= minCost[vRoot];
                parent[vRoot] = uRoot;
            }
            minCost[uRoot] &= edge[2];
        }

        int[] result = new int[query.length];
        for (int i = 0; i < query.length; i++) {
            int u = query[i][0], v = query[i][1];
            int uRoot = find(u), vRoot = find(v);

            if (u == v) result[i] = 0;
            else if (uRoot != vRoot) result[i] = -1;
            else result[i] = minCost[uRoot];
        }

        return result;
    }
}
```
```Go []
func find(node int, parent []int) int {
    if parent[node] < 0 {
        return node
    }
    parent[node] = find(parent[node], parent)
    return parent[node]
}

func minimumCost(n int, edges [][]int, query [][]int) []int {
    parent := make([]int, n)
    minCost := make([]int, n)
    for i := range parent {
        parent[i] = -1
        minCost[i] = -1
    }

    for _, edge := range edges {
        uRoot, vRoot := find(edge[0], parent), find(edge[1], parent)
        if uRoot != vRoot {
            minCost[uRoot] &= minCost[vRoot]
            parent[vRoot] = uRoot
        }
        minCost[uRoot] &= edge[2]
    }

    result := make([]int, len(query))
    for i, q := range query {
        uRoot, vRoot := find(q[0], parent), find(q[1], parent)
        if q[0] == q[1] {
            result[i] = 0
        } else if uRoot != vRoot {
            result[i] = -1
        } else {
            result[i] = minCost[uRoot]
        }
    }
    return result
}
```

['Union Find', 'Graph', 'Python', 'C++', 'Java', 'Go']