Kruskal || UnionFind || MSP || Java
Intuition\nWhat we need to do in this question is that we need to find the minimum spanning trees repeatedly inckuding and skipping some edges to find out what 
# Intuition\nWhat we need to do in this question is that we need to find the minimum spanning trees repeatedly inckuding and skipping some edges to find out what edges are crucial and what are pseudo crucial . The edges that arte  crucial are those if not taken will lead to an increase in the weight of the spanning tree and the pseudo crucial are those that are not crucial but if includede in the spanni g tree will not effect the weight of the mi nimum spannning tree . \n\nLets start the question first we will need a sorted array of edges sorted by thheir weight . Now we can sort the original edges list but this way we will loose the originla index pf the array that we need p return in the answer so we will make a new array and stoe all the values of edges as it is but also add the originla index of the edge that we  were given by the question . \n\nNo we will sort this new edges list by the weight and calculate the msp by kruskal algorithm in classic way using union find by rank . After getting the msp we will iterate over all the edges and find the weight of the msp skipping that edge . If this weight is greated that msp we will add this to the first list of our answer tat represents a crucial edge . If the weight is not more that the msp thenw we will force include that edge in out kruskal and check if the msp weight is still the same if it is we will add this edge to the second list of our answer that represnts pseudo critical edges . \n\nThen we will return the ans .\nI am not including the defination of kruskal and union find because if you dont know that you should not be jumping to this question .\n\n# Complexity\n- Time complexity:(E^2 + E log E) first term for kruskal for all edges and second for the sorting.\n\n- Space complexity:O(E + N) E for the new edges and N for the union find\n\n# Code\n```java []\nclass Solution {\n    private int N;\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        N = n;\n        List<List<Integer>> res = new ArrayList<>();\n        for(int i = 0 ; i < 2 ; i++) res.add(new ArrayList<>());\n        int edgeLength = edges.length;\n        int[][] newEdges = new int[edgeLength][4];\n        for(int i = 0 ; i < edgeLength ; i++){\n            for(int j = 0 ; j < 3 ; j++){\n                newEdges[i][j] = edges[i][j];\n            }\n            newEdges[i][3] = i;\n        }\n\n        Arrays.sort(newEdges , Comparator.comparingInt(edge -> edge[2]));\n        int minWeight = kruskal(newEdges , -1 , -1);\n        for(int i = 0 ; i < edgeLength ; i++){\n            if(kruskal(newEdges , i , -1) > minWeight) res.get(0).add(newEdges[i][3]);\n            else if(kruskal(newEdges , -1 , i) == minWeight) res.get(1).add(newEdges[i][3]);\n        }\n        return res;   \n    }\n\n    private int kruskal(int[][] edges , int skip , int include){\n        int edgeLength = edges.length;\n        int totalEdges = 0;\n        int res = 0;\n\n        UnionFind uf = new UnionFind(N);\n        if(include != -1){\n            res += edges[include][2];\n            totalEdges++;\n            uf.union(edges[include][0] , edges[include][1]);\n        }\n\n        for(int i = 0 ; i < edgeLength ; i++){\n            if(i == skip) continue;\n            int u = edges[i][0];\n            int v = edges[i][1];\n            int w = edges[i][2];\n            int parentU = uf.find(u);\n            int parentV = uf.find(v);\n            if(parentU != parentV){\n                uf.union(u,v);\n                res += w;\n                totalEdges++;\n            }\n        }\n\n        if(totalEdges != N - 1) return Integer.MAX_VALUE;\n        return res;\n    }\n\n    class UnionFind {\n        int[] parent;\n        int[] rank;\n\n        public UnionFind(int n){\n            parent = new int[n];\n            rank = new int[n];\n            for(int i = 0 ; i < n ; i++){\n                parent[i] = i;\n                rank[i] = 0;\n            }\n        }\n\n        private int find(int i){\n            if(parent[i] == i) return parent[i];\n            return parent[i] = find(parent[i]);\n        }\n\n        private void union(int i , int j){\n            int parentI = find(i);\n            int parentJ = find(j);\n\n            if(parentI == parentJ) return;\n\n            if(rank[parentI] > rank[parentJ]) parent[parentJ] = parentI;\n            else if(rank[parentI] < rank[parentJ]) parent[parentI] = parentJ;\n            else{\n                parent[parentI] = parentJ;\n                rank[parentJ]++;\n            }\n        }\n    }\n}\n```
['Union Find', 'Graph', 'Sorting', 'Minimum Spanning Tree', 'Strongly Connected Component', 'Java']