Ex-Amazon explains a solution with Python and Java
Solution Video\nI have to take care of my kids all day. Usually I put a solution video for each question but today, it seems to be hard to create the video.\n\n
# Solution Video\nI have to take care of my kids all day. Usually I put a solution video for each question but today, it seems to be hard to create the video.\n\n### Please subscribe to my channel from here. I have 245 videos as of August 19th.\n\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n---\n\n# Approach\nI have limited time today, so I solved this quesion with Python and Java. This is based on Python. Other might be different a bit.\n\n1. **Initialize UnionFind Class:**\n   - Create a class named `UnionFind` to implement the Union-Find data structure.\n   - Initialize the class with the `size` of elements. Initialize `parent` as a list of indices and set each element\'s size to 1 and `max_size` to 1.\n\n2. **Define `find` Method:**\n   - Implement the `find` method within the `UnionFind` class.\n   - Given an element `x`, recursively find its root element and update its parent to the root.\n   - Return the root element.\n\n3. **Define `union` Method:**\n   - Implement the `union` method within the `UnionFind` class.\n   - Given elements `x` and `y`, find their root elements.\n   - If the roots are not the same, merge the smaller tree under the larger tree.\n   - Update the parent and size accordingly, and track the maximum size.\n\n4. **Initialize Variables:**\n   - Create a function named `findCriticalAndPseudoCriticalEdges` within the `Solution` class.\n   - Create a copy of the `edges` list named `sorted_edges` and append the index to each edge.\n   - Sort `sorted_edges` based on the edge weight using a lambda function.\n\n5. **Calculate Minimum Spanning Tree (MST) Weight:**\n   - Initialize an instance of the `UnionFind` class as `union_find_standard`.\n   - Initialize `minimum_spanning_tree_weight` as 0.\n   - Iterate through each edge `(u, v, weight, _)` in `sorted_edges`.\n     - If `union_find_standard.union(u, v)` connects the nodes, update `minimum_spanning_tree_weight` by adding the edge weight.\n\n6. **Find Critical and Pseudo-Critical Edges:**\n   - Initialize two empty lists `critical_edges` and `pseudo_critical_edges`.\n   - Iterate through each edge `(u, v, weight, i)` in `sorted_edges`.\n     - Initialize a temporary `UnionFind` instance as `union_find_temp` and a temporary weight `temp_weight` as 0.\n     - For each edge `(x, y, w_temp, j)` in `sorted_edges`, calculate the total weight `temp_weight` if the current edge is ignored.\n     - Check if `union_find_temp.max_size` is less than `n` or `temp_weight` is greater than `minimum_spanning_tree_weight`.\n       - If true, add `i` to `critical_edges` and continue.\n     - Otherwise, initialize a new `UnionFind` instance as `union_find_force` and initialize `force_weight` as `weight`.\n     - Perform union on `(u, v)` using `union_find_force` and iterate through all edges to calculate `force_weight` if the current edge is forced.\n     - Check if `force_weight` is equal to `minimum_spanning_tree_weight`.\n       - If true, add `i` to `pseudo_critical_edges`.\n\n7. **Return Result:**\n   - Return a list containing `critical_edges` and `pseudo_critical_edges`.\n\nThe code aims to find critical and pseudo-critical edges in a graph\'s minimum spanning tree (MST) using the Union-Find data structure. It sorts edges based on weight, calculates the MST weight, and checks for critical and pseudo-critical edges based on certain conditions.\n\n```python []\nclass Solution:\n\n    class UnionFind:\n        def __init__(self, size):\n            self.parent = list(range(size))\n            self.size = [1] * size\n            self.max_size = 1\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\n        def union(self, x, y):\n            root_x = self.find(x)\n            root_y = self.find(y)\n            if root_x != root_y:\n                if self.size[root_x] < self.size[root_y]:\n                    root_x, root_y = root_y, root_x\n                self.parent[root_y] = root_x\n                self.size[root_x] += self.size[root_y]\n                self.max_size = max(self.max_size, self.size[root_x])\n                return True\n            return False\n\n    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        sorted_edges = [edge.copy() for edge in edges]\n\n        for i, edge in enumerate(sorted_edges):\n            edge.append(i)\n\n        sorted_edges.sort(key=lambda x: x[2])\n\n        union_find_standard = self.UnionFind(n)\n        minimum_spanning_tree_weight = 0\n        for u, v, weight, _ in sorted_edges:\n            if union_find_standard.union(u, v):\n                minimum_spanning_tree_weight += weight\n\n        critical_edges = []\n        pseudo_critical_edges = []\n        for (u, v, weight, i) in sorted_edges:\n            union_find_temp = self.UnionFind(n)\n            temp_weight = 0\n            for (x, y, w_temp, j) in sorted_edges:\n                if i != j and union_find_temp.union(x, y):\n                    temp_weight += w_temp\n\n            if union_find_temp.max_size < n or temp_weight > minimum_spanning_tree_weight:\n                critical_edges.append(i)\n                continue\n\n            union_find_force = self.UnionFind(n)\n            force_weight = weight\n            union_find_force.union(u, v)\n            for (x, y, w_force, j) in sorted_edges:\n                if i != j and union_find_force.union(x, y):\n                    force_weight += w_force\n\n            if force_weight == minimum_spanning_tree_weight:\n                pseudo_critical_edges.append(i)\n\n        return [critical_edges, pseudo_critical_edges]\n```\n```java []\nimport java.util.*;\n\nclass Solution {\n    class UnionFind {\n        int[] parent;\n        int[] size;\n        int maxSize;\n\n        public UnionFind(int size) {\n            this.parent = new int[size];\n            this.size = new int[size];\n            for (int i = 0; i < size; i++) {\n                parent[i] = i;\n                this.size[i] = 1;\n            }\n            this.maxSize = 1;\n        }\n\n        public int find(int x) {\n            if (x != parent[x]) {\n                parent[x] = find(parent[x]);\n            }\n            return parent[x];\n        }\n\n        public boolean union(int x, int y) {\n            int rootX = find(x);\n            int rootY = find(y);\n            if (rootX != rootY) {\n                if (size[rootX] < size[rootY]) {\n                    int temp = rootX;\n                    rootX = rootY;\n                    rootY = temp;\n                }\n                parent[rootY] = rootX;\n                size[rootX] += size[rootY];\n                maxSize = Math.max(maxSize, size[rootX]);\n                return true;\n            }\n            return false;\n        }\n    }\n\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        List<List<Integer>> result = new ArrayList<>();\n        List<int[]> sortedEdges = new ArrayList<>();\n        for (int i = 0; i < edges.length; i++) {\n            sortedEdges.add(new int[]{edges[i][0], edges[i][1], edges[i][2], i});\n        }\n        Collections.sort(sortedEdges, Comparator.comparingInt(a -> a[2]));\n\n        UnionFind unionFindStandard = new UnionFind(n);\n        int minimumSpanningTreeWeight = 0;\n        for (int[] edge : sortedEdges) {\n            if (unionFindStandard.union(edge[0], edge[1])) {\n                minimumSpanningTreeWeight += edge[2];\n            }\n        }\n\n        List<Integer> criticalEdges = new ArrayList<>();\n        List<Integer> pseudoCriticalEdges = new ArrayList<>();\n        for (int[] edge : sortedEdges) {\n            UnionFind unionFindTemp = new UnionFind(n);\n            int tempWeight = 0;\n            for (int[] tempEdge : sortedEdges) {\n                if (edge[3] != tempEdge[3] && unionFindTemp.union(tempEdge[0], tempEdge[1])) {\n                    tempWeight += tempEdge[2];\n                }\n            }\n\n            if (unionFindTemp.maxSize < n || tempWeight > minimumSpanningTreeWeight) {\n                criticalEdges.add(edge[3]);\n                continue;\n            }\n\n            UnionFind unionFindForce = new UnionFind(n);\n            int forceWeight = edge[2];\n            unionFindForce.union(edge[0], edge[1]);\n            for (int[] forceEdge : sortedEdges) {\n                if (edge[3] != forceEdge[3] && unionFindForce.union(forceEdge[0], forceEdge[1])) {\n                    forceWeight += forceEdge[2];\n                }\n            }\n\n            if (forceWeight == minimumSpanningTreeWeight) {\n                pseudoCriticalEdges.add(edge[3]);\n            }\n        }\n\n        result.add(criticalEdges);\n        result.add(pseudoCriticalEdges);\n        return result;\n    }\n}\n```
['Java', 'Python3']