Java-MST & Kruskal Algorithm
Intuition\n Describe your first thoughts on how to solve this problem. \nWrote code to implement UnionFind aka Disjoint Set data structure. Calculate minimum co
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWrote code to implement UnionFind aka Disjoint Set data structure. Calculate minimum cost for Minimum Spanning Tree. And iterate edges to include and exculde to summerize critical and pseudo critical edges.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nImplement Disjoint Set data structure and calculate cost for MST. Iterate all edges to include and exclude; resulted in critical and pseudo critical edges.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(E.log(V))\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        Map<int[], Integer> edgeIndexMap = new HashMap();\n        for(int i = 0; i <edges.length; i++)\n            edgeIndexMap.put(edges[i], i);\n        List<Integer> criticalEdges = new ArrayList();\n        List<Integer> pseudoCriticalEdges = new ArrayList();\n        Arrays.sort(edges, (a,b)->a[2]-b[2]);\n        int minCost = MST(n, edges, null, null);\n        for(int[] edge:edges){\n            int excludeCost = MST(n, edges, null, edge);\n            if (excludeCost>minCost)\n                criticalEdges.add(edgeIndexMap.get(edge));\n            else{\n                int includeCost = MST(n, edges, edge, null);\n                if (includeCost == minCost)\n                    pseudoCriticalEdges.add(edgeIndexMap.get(edge));\n            }\n        }\n        return Arrays.asList(criticalEdges, pseudoCriticalEdges);\n    }\n    private int MST(int n, int[][] edges, int[] include, int[] exclude){\n        int cost=0;\n        UnionFind uf = new UnionFind(n);\n        if (include!=null){\n            uf.union(include[0], include[1]);\n            cost+=include[2];\n        }\n        for(int[] edge: edges)\n            if (edge!=exclude && (uf.union(edge[0], edge[1])))\n                cost+=edge[2];\n        return (uf.components==1)? cost: Integer.MAX_VALUE;\n    }\n}\nclass UnionFind{\n    int components;\n    int[] root;\n    UnionFind(int n){\n        components =n;\n        root = new int[n];\n        for(int i = 0; i<n; i++)\n            root[i]=i;\n    }\n    int find(int v){\n        if (root[v]==v)\n            return v;\n        return find(root[v]);\n    }\n    boolean union(int v1, int v2){\n        int ar1 = find(v1);\n        int ar2 = find(v2);\n        if (ar1==ar2)\n            return false;\n        root[ar1]=ar2;\n        components--;\n        return true;\n    }\n}\n```
['Java']