Simple Java Solution || Beginner Friendly || Easy to Understand 🔥
Approach\n\nKruskal algorithm + Union Find\n\n\nCertainly, in this approach, you iterate through all edges while simulating Kruskal\'s algorithm. For each edge,
# Approach\n```\nKruskal algorithm + Union Find\n```\n\nCertainly, in this approach, you iterate through all edges while simulating Kruskal\'s algorithm. For each edge, you skip it and create a new spanning tree. By comparing the new spanning tree\'s cost with the original minimum spanning tree\'s cost, you classify the edge as critical if the new cost surpasses the original or if excluding the edge causes disconnection. If the costs match, the edge is marked as pseudo-critical, subject to a subsequent check for inclusion while maintaining the minimum cost. This method helps determine critical edges that must be included, pseudo-critical edges that could be included, and non-critical edges that are safe to omit from the minimum spanning tree.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:  `O(E * V * log(E))` where `E` = number of edges\n`V` = number of vertices.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(E + V)`  where `E` = number of edges\n`V` = number of vertices.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    class UnionFind {\n        int[] root;\n        int count;\n\n        public UnionFind(int size) {\n            root = new int[size];\n            count = size;\n            for (int i = 0; i < size; i++) root[i] = i;\n        }\n\n        public int find(int x) {\n            if (root[x] == x) return x;\n            return root[x] = find(root[x]);\n        }\n\n        public void union(int x, int y) {\n            int rootX = find(x) , rootY = find(y);\n            if (rootX != rootY) {\n                root[rootX] = rootY;\n                count--;\n            }\n        }\n    }\n\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] oldedges) {\n        int[][] edges = new int[oldedges.length][4];\n\n        for (int i = 0; i < edges.length; i++) {\n            edges[i][0] = oldedges[i][0];\n            edges[i][1] = oldedges[i][1];\n            edges[i][2] = oldedges[i][2];\n            edges[i][3] = i;\n        }\n    \n        Arrays.sort(edges, (a, b) -> a[2] - b[2]);\n        int min = cost(n, edges, null, null);\n        List<Integer> criticals = new ArrayList<>();\n        List<Integer> pseudo = new ArrayList<>();\n\n        for (int i = 0; i < edges.length; i++) {\n            int[] edge = edges[i];\n            int costWithoutEdge = cost(n, edges, null, edge);\n            if (costWithoutEdge != min) {\n                criticals.add(edge[3]);\n            } else if (costWithoutEdge == min) {\n                int costWithEdge = cost(n, edges, edge, null);\n                if (costWithEdge == min) {\n                    pseudo.add(edge[3]);\n                }\n            }\n        }\n\n        List<List<Integer>> ans = new ArrayList<>();\n        ans.add(criticals);\n        ans.add(pseudo);\n        return ans; \n    }\n\n    public int cost(int n, int[][] edges, int[] pick, int[] skip) {\n        UnionFind uf = new UnionFind(n);\n\n        int ans = 0;\n\n        if (pick != null) {\n            ans += pick[2];\n            uf.union(pick[0], pick[1]);\n        }\n        \n        for (int[] edge: edges) {\n            if (skip != null) {\n                if (edge[0] == skip[0] && edge[1] == skip[1]) continue;\n            }\n            \n            if (uf.find(edge[0]) == uf.find(edge[1])) continue;\n            uf.union(edge[0], edge[1]);\n            ans += edge[2];\n            if (uf.count == 1) break;\n        }\n        return ans;\n    }\n}\n```
['Union Find', 'Graph', 'Sorting', 'Minimum Spanning Tree', 'Java']