[C++, Java, Python3] Union Find
Intuition\nWhen navigating the graph, we use bitwise AND operations between edges to calculate the path\'s cost. Additionally, we can reuse the same edges multi
# Intuition\nWhen navigating the graph, we use bitwise `AND` operations between edges to calculate the path\'s cost. Additionally, we can reuse the same edges multiple times. By performing bitwise `AND`, the cost may decrease or remain the same. Hence, our objective is to maximize edge utilization to minimize path cost. We can organize vertices into groups reachable via connected edges. Within each group, traversing any two nodes results in the same cost since we traverse all edges in the group, ensuring the minimum cost. Consequently, for each group of interconnected vertices, the cost remains constant, equivalent to the `AND` operation of all connecting edges within the group.\n\n# Approach\n* Perform union find on edges to find the groups of connected vertices\n* During the union-find operation, maintain a list called `weights` to represent the weight of each connected group. When performing a `union` operation between two vertices, compute the new weight of the group by performing a bitwise AND operation between the existing weight of each group and the cost of the edge connecting them. This process updates the cost of the group of vertices to reflect the addition of the new edge\n* All `weights` are initialized to `131071`. `131071` is chosen because it is `11111111111111111` in binary and is greater than `10^5`.\n* When returning result for a query if s<sub>i</sub> is equal to t<sub>i</sub> return 0 because start and target are same\n* If s<sub>i</sub> and t<sub>i</sub> don\'t belong to the same group return -1\n* If s<sub>i</sub> and t<sub>i</sub> are members of the same group, return the result of performing the `AND` operation on all edges within that group.\n\n# Complexity\n- Time complexity: $O(N)$. Time complexity of union find with path compresson and rank is close to $O(N)$\n- Space complexity: $O(N)$. We create new arrays in the `DSU` class which incur a space complexity of $O(N)$.\n\n### **Note**: The code shared here uses *rank* and *path compression* both to lower time complexity. If you don\'t use *rank*, time complexity will be $O(N \\cdot logN)$.\n\n# Code\n**Python3**:\n```\nclass DSU:\n    def __init__(self, n):\n        self.parent = list(range(n))\n        self.rank = [0] * n\n        self.weights = [131071] * n\n    def find(self, x):\n        if x != self.parent[x]:\n            self.parent[x] = self.find(self.parent[x])\n        return self.parent[x]\n    def union(self, x, y, weight):\n        xx, yy = self.find(x), self.find(y)\n        if self.rank[xx] < self.rank[yy]:\n            self.parent[xx] = yy        \n        else:\n            self.parent[yy] = xx\n        self.weights[xx] = self.weights[yy] = self.weights[xx] & self.weights[yy] & weight\n        if self.rank[xx] == self.rank[yy]:\n            self.rank[xx] += 1\n    def minimum_cost_of_walk(self, x, y):\n        if x == y: return 0\n        if self.find(x) != self.find(y): return -1\n        return self.weights[self.find(x)]\n\nclass Solution:\n    def minimumCost(self, n, edges, query):\n        uf = DSU(n)\n        for x, y, z in edges:\n            uf.union(x, y, z)\n        return [uf.minimum_cost_of_walk(x, y) for x, y in query]\n```\n\n**C++**:\n```\nclass DSU {\nprivate:\n    vector<int> parent, rank, weights;\npublic:\n    DSU(int n) {\n        parent = vector<int>(n);\n        rank = vector<int>(n, 0);\n        weights = vector<int>(n, 131071);\n        for (int i = 0; i < n; ++i)\n            parent[i] = i;\n    }\n    int find(int x) {\n        if (x != parent[x])\n            parent[x] = find(parent[x]);\n        return parent[x];\n    }\n    void union_(int x, int y, int weight) {\n        int xx = find(x);\n        int yy = find(y);\n        if (rank[xx] < rank[yy])\n            parent[xx] = yy;\n        else\n            parent[yy] = xx;\n        weights[xx] = weights[yy] = weights[xx] & weights[yy] & weight;\n        if (rank[xx] == rank[yy])\n            rank[xx]++;\n    }\n    int minimumCostOfWalk(int x, int y) {\n        if (x == y) return 0;\n        if (find(x) != find(y)) return -1;\n        return weights[find(x)];\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {\n        DSU uf(n);\n        for (auto& edge : edges)\n            uf.union_(edge[0], edge[1], edge[2]);\n        vector<int> result;\n        for (auto& q : query)\n            result.push_back(uf.minimumCostOfWalk(q[0], q[1]));\n        return result;\n    }\n};\n```\n\n**Java**:\n```\nclass DSU {\n    int[] parent, rank, weights;\n    public DSU(int n) {\n        parent = new int[n];\n        rank = new int[n];\n        weights = new int[n];\n        Arrays.fill(weights, 131071);\n        for (int i = 0; i < n; i++)\n            parent[i] = i;\n    }\n    public int find(int x) {\n        if (x != parent[x])\n            parent[x] = find(parent[x]);\n        return parent[x];\n    }\n    public void union(int x, int y, int weight) {\n        int xx = find(x);\n        int yy = find(y);\n        if (rank[xx] < rank[yy])\n            parent[xx] = yy;\n        else\n            parent[yy] = xx;\n        weights[xx] = weights[yy] = weights[xx] & weights[yy] & weight;\n        if (rank[xx] == rank[yy])\n            rank[xx]++;\n    }\n    public int minimumCostOfWalk(int x, int y) {\n        if (x == y)\n            return 0;\n        if (find(x) != find(y))\n            return -1;\n        return weights[find(x)];\n    }\n}\nclass Solution {\n    public int[] minimumCost(int n, int[][] edges, int[][] query) {\n        DSU uf = new DSU(n);\n        for (int[] edge : edges)\n            uf.union(edge[0], edge[1], edge[2]);\n        int[] result = new int[query.length];\n        for (int i = 0; i < query.length; i++)\n            result[i] = uf.minimumCostOfWalk(query[i][0], query[i][1]);\n        return result;\n    }\n}\n```
['Python', 'C++', 'Java']