🔥Python3🔥 Union-find (Template + Explanations)
The main idea is for each connected graph, the minimum cost is the bitwise AND of all the weights in this graph.\nUsing UnionFind to get the connected graph and
The main idea is for each connected graph, the ```minimum cost``` is the **bitwise AND of all the weights** in this graph.\nUsing UnionFind to get the connected graph and the bitwise AND of all the weights in the graph.\n\nGrouping connected elements can be done using DFS/BFS/Union-find, I personally like Union-find because it makes the most sense, and very easy to implement using a template. If you don\'t know about union-find or don\'t have a good template, I put the best one I know below which I used a lot.\n\n**Basic Union-find template**\n\n```python\n# UF is a hash map where you can find the root of a group of elements giving an element.\n# A key in UF is a element, UF[x] is x\'s parent.\n# If UF[x] == x meaning x is the root of its group.\nUF = {}\n\n# Given an element, find the root of the group to which this element belongs.\ndef find(x):\n    # this may be the first time we see x, so set itself as the root.\n    if x not in UF:\n        UF[x] = x\n    # If x == UF[x], meaning x is the root of this group.\n    # If x != UF[x], we use the find function again on x\'s parent UF[x] \n    # until we find the root and set it as the parent (value) of x in UF.\n    if x != UF[x]:\n        UF[x] = find(UF[x])\n    return UF[x]\n\n# Given two elements x and y, we know that x and y should be in the same group, \n# this means the group that contains x and the group that contains y \n# should be merged together if they are currently separate groups.\n# So we first find the root of x and the root of y using the find function.\n# We then set the root of y (rootY) as the root of the root of x (rootX).\ndef union(x, y):\n\n    rootX = find(x)\n    rootY = find(y)\n    # set the root of y (rootY) as the root of the root of x (rootX)\n    UF[rootX] = rootY\n```\n\n**Solving the problem using the template with a little bit modification to calculate the weights**\n\n```python\nclass Solution:\n    def minimumCost(self, n: int, edges: List[List[int]], Q: List[List[int]]) -> List[int]:\n        UF = {}\n        # Used to store the total weight of each connected graph.\n        graphWeight = defaultdict(int)\n\n        def find(x):\n            # we also set the graphweight of this node to (1<<32)-1, since we are doing bitwise AND.\n            if x not in UF:\n                UF[x] = x\n                graphWeight[x] = (1<<32)-1\n            if x != UF[x]:\n                UF[x] = find(UF[x])\n            return UF[x]\n\n        def union(x, y):\n            rootX = find(x)\n            rootY = find(y)\n            # Union the weights of the two roots\n            graphWeight[rootY] = graphWeight[rootX] & graphWeight[rootY]\n            UF[rootX] = rootY\n    \n\n        # Union the connected nodes, and update the weight of the root.\n        for s,e,w in edges:\n            union(s,e)\n            root = find(s)\n            # update the weight of the root to include this edge\n            graphWeight[root] &=  w\n        \n        res = []\n        for s,e in Q:\n            if find(s) != find(e): # these two node are ins sperate graphs\n                res.append(-1)\n            elif s==e:\n                res.append(0) # when nodes are the same, weight is 0 but not the total weight of the connected graph\n            else:\n                res.append(graphWeight[find(s)]) # Use the total weight of this connected graph\n        return res\n```\n\n**Connect with me on [LinkedIn](https://www.linkedin.com/in/meida-chen-938a265b/)** if you\'d like to discuss other related topics\n\n\uD83C\uDF1F If you are interested in **Machine Learning** || **Deep Learning** || **Computer Vision** || **Computer Graphics** related projects and topics, check out my **[YouTube Channel](https://www.youtube.com/@meidachen8489)**! Subscribe for regular updates and be part of our growing community.
[]