Video Solution | Explanation With Drawings | Java | C++
Intuition, approach and complexity discussed in detail in video solution.\nhttps://youtu.be/PafEXCOUvWk\n\n\n# Code\nJava\n\nclass Solution {   \n    private cl
# Intuition, approach and complexity discussed in detail in video solution.\nhttps://youtu.be/PafEXCOUvWk\n\n\n# Code\nJava\n```\nclass Solution {   \n    private class DSU{\n        private Integer parent[] = null, rank[] = null;\n        public int maxSize;\n        public DSU(int size){\n            parent = new Integer[size];\n            rank = new Integer[size];\n            Arrays.fill(rank, 1);\n            maxSize = 0;\n            for(int vert = 0; vert < size; vert++){\n                parent[vert] = vert;\n            }\n\n        }\n        public int find(int vert){\n            if(parent[vert] == vert) return vert;\n            return parent[vert] = find(parent[vert]);\n        }\n        void join(int vert1, int vert2){\n            int rep1 = find(vert1);\n            int rep2 = find(vert2);\n            if(rep1 != rep2){\n                int rank1 = rank[rep1], rank2 = rank[rep2];\n                if(rank1 < rank2){\n                    swap(rep1, rep2);\n                }\n                parent[rep2] = rep1;\n                rank[rep1] += rank[rep2];\n                maxSize = Math.max(maxSize, rank[rep1]);\n            }\n        }\n    }       \n    private void swap(int val1, int val2){\n        int temp = val1;\n        val1 = val2;\n        val2 = temp;\n    }       \n   public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        int sz = edges.length;\n        int[][] egWithIndx = new int[sz][4];\n        for(int indx = 0; indx < sz; indx++){\n            egWithIndx[indx][0] = edges[indx][0];\n            egWithIndx[indx][1] = edges[indx][1];\n            egWithIndx[indx][2] = edges[indx][2];\n            egWithIndx[indx][3] = indx;\n        }\n        Arrays.sort(egWithIndx, (a, b)->(a[2] - b[2]));\n\n        DSU ogMST = new DSU(n);\n        int ogWt = 0;\n\n        for(int eIndx = 0; eIndx < sz; eIndx++){\n            int []eg = egWithIndx[eIndx];\n            if(ogMST.find(eg[0]) != ogMST.find(eg[1])){\n                ogMST.join(eg[0], eg[1]);\n                ogWt += eg[2];\n            }    \n        }\n\n        List<List<Integer>> result = new ArrayList<>();\n        result.add(new ArrayList<>());\n        result.add(new ArrayList<>());\n        for(int eIndx = 0; eIndx < sz; eIndx++){\n            DSU newSpT = new DSU(n);\n            int newWt = 0;\n            for(int newEg = 0; newEg < sz; newEg++){\n                if(newEg == eIndx)continue;\n                int eg[] = egWithIndx[newEg];\n                if(newSpT.find(eg[0]) != newSpT.find(eg[1])){\n                    newSpT.join(eg[0], eg[1]);\n                    newWt += eg[2];\n                }    \n            }\n            if(newSpT.maxSize < n || newWt > ogWt){\n                int eg[] = egWithIndx[eIndx];\n                result.get(0).add(eg[3]);\n            }else{\n                DSU newSpT1 = new DSU(n);\n                newSpT1.join(egWithIndx[eIndx][0], egWithIndx[eIndx][1]);\n                int newWt1 = egWithIndx[eIndx][2];\n                for(int newEg = 0; newEg < sz; newEg++){\n                    if(newEg == eIndx)continue;\n                    int []eg = egWithIndx[newEg];\n                    if(newSpT1.find(eg[0]) != newSpT1.find(eg[1])){\n                        newSpT1.join(eg[0], eg[1]);\n                        newWt1 += eg[2];\n                    }    \n                }\n                if(newSpT1.maxSize == n && newWt1 == ogWt){\n                    int []eg = egWithIndx[eIndx];\n                    result.get(1).add(eg[3]);\n                }\n            }\n\n        }\n        return result;  \n    }\n}\n```\nC++\n```\nclass Solution {\nprivate: \nclass DSU{\nprivate:\n        vector<int> parent, rank;\npublic: \n        int maxSize;\n        DSU(int size){\n            maxSize = 0;\n            parent.resize(size);\n            rank.resize(size, 1);\n            for(int vert = 0; vert < size; vert++){\n                parent[vert] = vert;\n            }\n        }\npublic:\n   int find(int vert){\n       if(parent[vert] == vert) return vert;\n       return parent[vert] = find(parent[vert]);\n   }\n   void join(int vert1, int vert2){\n       int rep1 = find(vert1);\n       int rep2 = find(vert2);\n       if(rep1 != rep2){\n           int rank1 = rank[rep1], rank2 = rank[rep2];\n           if(rank1 < rank2){\n               swap(rep1, rep2);\n           }\n           parent[rep2] = rep1;\n           rank[rep1] += rank[rep2];\n           maxSize = max(maxSize, rank[rep1]);\n       }\n   }  \n        \n};    \npublic:\n    \n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        int sz = edges.size();\n        vector<vector<int>> egWithIndx(sz, vector<int>(4));\n        for(int indx = 0; indx < sz; indx++){\n            egWithIndx[indx] = edges[indx];\n            egWithIndx[indx].push_back(indx);\n        }\n        sort(egWithIndx.begin(), egWithIndx.end(), [](const vector<int> & eg1, vector<int>& eg2)->bool{\n            return eg1[2] < eg2[2];\n        });\n        DSU ogMST(n);\n        int ogWt = 0;\n        for(int eIndx = 0; eIndx < sz; eIndx++){\n            vector<int> &eg = egWithIndx[eIndx];\n            if(ogMST.find(eg[0]) != ogMST.find(eg[1])){\n                ogMST.join(eg[0], eg[1]);\n                ogWt += eg[2];\n            }    \n        }\n        cout<<"ogWt "<<ogWt<<endl;\n\n        vector<vector<int>> result(2);\n        for(int eIndx = 0; eIndx < sz; eIndx++){\n            auto &eg = egWithIndx[eIndx];\n            DSU newSpT(n);\n            int newWt = 0;\n            for(int newEg = 0; newEg < sz; newEg++){\n                if(newEg == eIndx)continue;\n                vector<int> &eg = egWithIndx[newEg];\n                if(newSpT.find(eg[0]) != newSpT.find(eg[1])){\n                    newSpT.join(eg[0], eg[1]);\n                    newWt += eg[2];\n                }    \n            }\n            if(newSpT.maxSize < n || newWt > ogWt){\n                result[0].push_back(eg[3]);\n                cout<<"maxSize"<<newSpT.maxSize<<" newWt "<<newWt<<endl;\n            }else{\n                DSU newSpT1(n);\n                vector<int> &eg = egWithIndx[eIndx];\n                newSpT1.join(eg[0], eg[1]);\n                int newWt1 = eg[2];\n                for(int newEg = 0; newEg < sz; newEg++){\n                    if(newEg == eIndx)continue;\n                    vector<int> &eg = egWithIndx[newEg];\n                    if(newSpT1.find(eg[0]) != newSpT1.find(eg[1])){\n                        newSpT1.join(eg[0], eg[1]);\n                        newWt1 += eg[2];\n                    }    \n                }\n                if(newSpT1.maxSize == n && newWt1 == ogWt){\n                    result[1].push_back(eg[3]);\n                }\n            }\n\n        }\n        return result;\n    }\n};\n```
['C++']