Kruskal's Algo || Python3
KRUSKAL\'S ALGORITHM (Greedy Algorithm)\n\nImplements a Minimum Spanning Tree (MST) approach using the Kruskal\'s algorithm.\n\nVery Easy Solution:-Python3\n\nT
**KRUSKAL\'S ALGORITHM** *(Greedy Algorithm)*\n\n*Implements a Minimum Spanning Tree (MST) approach using the Kruskal\'s algorithm.*\n\n**Very Easy Solution:-Python3**\n\n**Time complexity:-** \n*Let\'s analyze the different parts of code:-*\n\n*1:- Initializing par, ans, and wgt lists: This operation takes O(n) time.*\n\n*2:-  The union function: The find operation inside the union function can take up to O(log n) time in the worst case due to path compression. Since it is called for each edge in the edges list, the total time complexity for this step is O(m * log(n)), where m is the number of edges.*\n\n*3:- The findwgt function: The find operation inside the findwgt function can also take up to O(log n) time in the worst case. Since it is called for each query in the queries list, the total time complexity for this step is O(q * log(n)), where q is the number of queries.*\n\n*4:- Finally, returning the result using map: Mapping over the queries list takes O(q) time.*\n\n*Therefore, the overall time complexity of this code is O(n + m * log(n) + q * log(n)), where n is the number of nodes, m is the number of edges, and q is the number of queries.*\n\n**Space Complexity:-**\n*Let\'s consider the space used by different components:*\n\n*1:- par, ans, and wgt lists: These lists each have a size of n, so they collectively use O(n) space.*\n\n*2:- Recursive stack space for the find function: Since the find function is implemented recursively, it uses additional space on the call stack. In the worst case, the depth of the call stack can be O(n) due to path compression, so the space complexity for the call stack is O(n).*\n\n*3:- Other variables used within functions: These variables use constant space and do not contribute significantly to the overall space complexity.*\n\n*Therefore, the overall space complexity of this code is O(n) due to the lists par, ans, and wgt, and O(n) additional space for the recursive call stack, resulting in a total space complexity of O(n).*\n\n\n\n\n```\nclass Solution:\n    def minimumCost(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n        # Define the find function to find the parent node of a given node\n        def find(node: int) -> int:\n            # If the node is its own parent, return the node\n            if node == par[node]: return node\n            # Apply path compression and return the parent node\n            par[node] = find(par[node])\n            return par[node]\n        \n        # Define the union function to merge two nodes and update their weights\n        def union(u: int, v: int, w: int) -> int:\n            # Find the parents of the two nodes\n            x, y = find(u), find(v)\n            # Update the weight of the parent node\n            wgt[y] &= wgt[x] & w\n            # Set the parent of the first node to be the second node\n            par[x] = y\n        \n        # Define the findwgt function to find the weight of a query\n        def findwgt(query: list) -> int:\n            s, t = query\n            # If the source and target nodes are the same, return 0\n            if s == t: return 0\n            # If the source and target nodes have different parents, return -1\n            if find(s) != find(t): return -1\n            # Return the weight of the parent node\n            return wgt[find(s)]\n        \n        # Initialize parent, answer, and weight lists\n        par, ans, wgt = list(range(n)), [], [(1<<31)-1] * n\n        \n        # Apply union operation on each edge\n        for edge in edges:\n            union(*edge)\n        \n        # Return the weights for each query using the findwgt function\n        return map(findwgt, queries)\n\n```
['Greedy', 'Python', 'Python3']