🤩 Python Union Find Clear Explanation
Intuition\n\nBitwise AND all vertexes weights in a group.\n\n\n\nIn group 1, \n\nfrom 0 to 1, minimum is 1\nfrom 0 to 3, minimum is 1\nfrom 0 to 2, minimum is 1
# Intuition\n\nBitwise AND all vertexes weights in a group.\n\n![CleanShot 2024-04-07 at 20.54.51.png](https://assets.leetcode.com/users/images/d643e1ee-75f2-4b29-8f0b-4ed24fa4f3f9_1712494695.0668368.png)\n\nIn group 1, \n\nfrom 0 to 1, minimum is 1\nfrom 0 to 3, minimum is 1\nfrom 0 to 2, minimum is 1\nfrom 1 to 2, minimum is 1\nfrom 2 to 3, minimum is 1\n\nfrom 3 to 4, result is -1 (because you can\'t cross the group)\n\n# Reason\n\nA walk can defined as follows:\n\n![CleanShot 2024-04-07 at 20.54.51.png](https://assets.leetcode.com/users/images/f0c565e4-c871-4f11-8b91-adc77cc6537f_1712495192.8983207.png)\n\nTo get the minimum, you want to bitwise AND as many walk as you want in a group.\n\n\n# Approach\n\n1. Group vertexes using Union Find.\n2. For each group, bitwise AND every weights and store in an array.\n3. For each query, get the bitwise AND of the group => array[group].\n\n# Code\n\n```Python []\nclass Solution:\n    def minimumCost(self, n, edges, query):\n        bitand = [2**31 - 1] * n\n        p = list(range(n))\n\n        def find(x):\n            if x != p[x]:\n                p[x] = find(p[x])\n            return p[x]\n\n        def union(x, y):\n            px = find(x)\n            py = find(y)\n            if px != py:\n                p[py] = px\n\n        for u, v, w in edges:\n            union(u, v)\n\n        for u, v, w in edges:\n            group = find(u)\n            bitand[group] &= w\n\n        res = []\n        for u, v in query:\n            if u == v: res.append(0); continue\n            group1, group2 = find(u), find(v)\n            if group1 != group2:\n                res.append(-1)\n            else:\n                res.append(bitand[group1])\n        return res\n```\n```Python&nbsp;With&nbsp;Code&nbsp;Explanation []\nclass Solution:\n    def minimumCost(self, n, edges, query):\n        # bitand for each group (2**31 - 1 fits largest input for bit 1)\n        bitand = [2**31 - 1] * n\n        \n        # Start of Union Find Data Structure\n        # used to store group\n        p = list(range(n))\n\n        def find(x):\n            if x != p[x]:\n                p[x] = find(p[x])\n            return p[x]\n\n        def union(x, y):\n            px = find(x)\n            py = find(y)\n            if px != py:\n                p[py] = px\n\n        # Start of Union Find Data Structure\n\n        # Grouping\n        # eg: Example 1 => p = [0, 0, 0, 0, 1] (vertex 0 - 3 belongs to a group, vertex 4 belongs to a group)\n        # eg: Example 2 => p = [0, 0, 0]\n        for u, v, w in edges:\n            union(u, v)\n\n        # Bitwise AND groups\n        # because AND with all the vertexes in a group will give the most min result\n        # eg: Example 1 => group 1 weights = (7, 7, 1) = (111 & 111 & 001) = (001)\n        # eg: Example 2 => group 1 weights = (15, 7, 6, 1) = (1111 & 0111 & 0110 & 0001) = (0000)\n        for u, v, w in edges:\n            group = find(u)\n            bitand[group] &= w\n\n        # construct output using precomputed bitand result\n        res = []\n        for u, v in query:\n            if u == v: res.append(0); continue\n            group1, group2 = find(u), find(v)\n            if group1 != group2:\n                res.append(-1)\n            else:\n                res.append(bitand[group1])\n        return res\n```\n\nUpvote for fun.
['Python', 'Python3']