Kruskal Solution using Union Find 🕵️‍♂️ Finding Critical and Pseudo-Critical Edges in a MST🍕
Intuition\n When I first saw this problem, I thought, "Let\'s just remove edges one by one and see what happens."\n Turns out, that\'s pretty much the plan! Som
# Intuition\n When I first saw this problem, I thought, "Let\'s just remove edges one by one and see what happens."\n Turns out, that\'s pretty much the plan! Some edges are like the last slice of pizza\u2014take them away,\n and everything falls apart (critical). Others are just like the second slice\u2014nice to have but not essential (pseudo-critical).\n\n# Approach\n1. MST Construction: Start by building the MST (Minimum Spanning Tree) using Kruskal\'s algorithm. \n    This gives us the baseline, like knowing the number of calories in that pizza.\n 2. Identify Critical Edges: Remove an edge, and if the MST crumbles or the weight increases, it\'s critical\u2014\n    like taking away the Wi-Fi from a group of teenagers.\n 3. Identify Pseudo-Critical Edges: Force an edge into the MST and check if the MST weight remains the same.\n    If it does, the edge is pseudo-critical\u2014kind of like that friend who insists on being in every group photo \n    but doesn\'t really change the vibe.\n 4. Union-Find Magic: Use the Union-Find data structure to efficiently manage connected components,\n    like being the bouncer at an exclusive club, deciding who gets to join the party.\n\n# Complexity\n- Time complexity: O(E^2 log V) because we\u2019re re-building the MST for each edge. It\u2019s like checking every slice of pizza \n   to see which one is most critical to your happiness.\n - Space complexity: O(V + E) for storing the parent and rank arrays in Union-Find and the edge list\u2014just enough space to \n   keep track of all the important stuff without getting lost.\n\n\n# Code\n```python3 []\nclass UnionFind:\n    def __init__(self,n):\n        self.par = [i for i in range(n)]\n        self.rank = [1] * n\n    \n    def find(self,v1):\n        while v1 != self.par[v1]:\n            self.par[v1] = self.par[self.par[v1]]\n            v1 = self.par[v1]\n        return v1\n    def union(self,v1,v2):\n        p1,p2 = self.find(v1), self.find(v2)\n        if p1 == p2:\n            return False\n        if self.rank[p1] > self.rank[p2]:\n            self.par[p2] = p1\n            self.rank[p1] += self.rank[p2]\n        else:\n            self.par[p1] = p2\n            self.rank[p2] += self.rank[p1]\n        return True\n\n\nclass Solution:\n    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        for i , e in enumerate(edges):\n            e.append(i) #[src, dest,weight,original_index]\n\n        edges.sort(key = lambda e:e[2])\n\n        mst_w = 0\n        uf = UnionFind(n)\n        for v1,v2,w,i in edges:\n            if uf.union(v1,v2):\n                mst_w += w\n\n        critical, pseudo = [],[]\n    \n        for n1,n2,e_weight,i in edges:\n            weight =  0\n            uf = UnionFind(n)\n            for v1,v2,w,j in edges:\n                if i!=j and uf.union(v1,v2):\n                    weight += w\n            if max(uf.rank) != n or weight > mst_w:\n                critical.append(i)\n                continue\n            uf = UnionFind(n)\n            uf.union(n1,n2) \n            weight = e_weight\n            for v1,v2,w,j in edges:\n                if uf.union(v1,v2):\n                    weight += w\n            if weight == mst_w:\n                pseudo.append(i)\n        return [critical, pseudo]\n\n\n            \n\n```
['Union Find', 'Graph', 'Sorting', 'Minimum Spanning Tree', 'Python', 'Python3']