MST using Kruskal Algorithm with Disjoint Sets
Idea The cost in making the MST is fist found, then based on definition \nOn removing any edge from our graph ,if we make a new MST and the cost of that MST com
**Idea** The cost in making the MST is fist found, then based on definition \nOn removing any edge from our graph ,if we make a new MST and the cost of that MST comes greater than our previous cost , then the edge is a critical edge\nOn adding any edge to our graph, if we make a new MST from the graph and find that the MST is already containing them (otherwise condition) then it is pseudo critcal \nJust think of it as {pseudo critical edges} = MST - {critcial edges}\nThe code for the given can be optimized using PriorityQueues ,but I have considered as simple considering in O(n^2)\n**Code**\n```\nclass Solution {\n    class DisjointSets{\n        class Node{\n            int data;\n            int rank;\n            Node parent;\n        }\n        HashMap<Integer,Node>nodemap = new HashMap<>();\n        int count;\n        void makeSet(int data_){\n            Node node = new Node(); \n            node.data = data_; node.parent = node; node.rank = 0;\n            nodemap.put(data_,node);\n        }\n        public Node find(Node node){\n            if(node == node.parent) return node;\n            node.parent = find(node.parent);\n            return node.parent;\n        }\n        public int findParent(int node){\n            return find(nodemap.get(node)).data;\n        }\n        public void union(int data1,int data2){\n            Node node1 = nodemap.get(data1),node2 = nodemap.get(data2);\n            Node parent1 = find(node1),parent2 = find(node2);\n            if(parent1 == parent2) return;\n             if(parent1.rank >= parent2.rank){\n                parent1.rank = (parent1.rank == parent2.rank)?parent1.rank + 1: parent1.rank;\n                parent2.parent = parent1;\n            }\n             else{\n                parent1.parent = parent2;\n                }\n            count--;\n        }\n    }\n    public int costMST(int n,int [][]edges,int []include,int []exclude){\n        DisjointSets ds = new DisjointSets();\n        ds.count = n;\n        for(int i=0;i<n;i++){\n            ds.makeSet(i);\n        }\n        int finalCost = 0;\n        if(include!=null){\n            ds.union(include[0],include[1]);\n            finalCost+=include[2];\n        }\n        for(int []edge : edges){\n            if(edge!=exclude && ds.findParent(edge[0])!=ds.findParent(edge[1])){\n                ds.union(edge[0],edge[1]);\n                finalCost+=edge[2];\n            }\n        }\n        return ds.count == 1? finalCost : Integer.MAX_VALUE;\n    }\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        List<Integer>critical = new ArrayList<>();\n        List<Integer>pseudo = new ArrayList<>();\n        HashMap<int[],Integer>edgeMap = new HashMap<>();\n        int counter = 0;\n        for(int []e : edges){\n            edgeMap.put(e,counter);\n            counter++;\n        }\n        Arrays.sort(edges,(edge1, edge2)-> Integer.compare(edge1[2],edge2[2]));\n        int minCost = costMST(n,edges,null,null);\n        for(int []edge : edges){\n            int exclusionCost = costMST(n,edges,null,edge);\n            if(exclusionCost > minCost){\n                critical.add(edgeMap.get(edge));\n            }\n            else{\n                int inclusionCost = costMST(n,edges,edge,null);\n                if(inclusionCost == minCost){\n                    pseudo.add(edgeMap.get(edge));\n                }\n            }\n        }\n        List<List<Integer>>finalRes = new ArrayList<>();\n        finalRes.add(critical);\n        finalRes.add(pseudo);\n        return finalRes;\n    }\n}\n```
[]