Using Disjoint set.
Intuition\nUsing Disjoint Set Union.\nKrushkal\'s Algorithim.\n\n\n\n\n\nJava []\nclass Solution {\n    public void union(int u, int v, int[] parent) {\n       
# Intuition\nUsing Disjoint Set Union.\nKrushkal\'s Algorithim.\n\n\n![c0504eaf-5fb8-4a1d-a769-833262d1b86e_1674433591.3836212.webp](https://assets.leetcode.com/users/images/4774f259-a0a2-4c97-af45-daf5e4d5b24e_1679166662.242037.webp)\n\n\n```Java []\nclass Solution {\n    public void union(int u, int v, int[] parent) {\n        int pu = find(u, parent);\n        int pv = find(v, parent);\n        if(pu != pv) {\n            parent[pv] = pu;\n        }\n    }\n\n    public int find(int node, int[] parent) {\n        if(parent[node] == node) {\n            return node;\n        }\n        return find(parent[node], parent);\n    }\n\n    public int mst(int n, int[][] edges, int includeEdge[], int excludeEdge[]) {\n\n        int[] parent = new int[n];\n        for(int i = 0; i < n; i++) {\n            parent[i] = i;\n        }\n        int ans = 0;\n        int size = 0;\n        if(includeEdge != null) {\n            int parent1 = find(includeEdge[0], parent);\n            int parent2 = find(includeEdge[1], parent);\n            union(parent1, parent2, parent);\n            ans += includeEdge[2];\n            size += 1;\n        }\n        \n        for(int[] edge : edges) {\n            if(excludeEdge != null && edge[0] == excludeEdge[0] && edge[1] == excludeEdge[1] && edge[2] ==  excludeEdge[2]) {\n                continue;\n            }\n            if(includeEdge != null && edge[0] == includeEdge[0] && edge[1] == includeEdge[1] && edge[2] ==  includeEdge[2]) {\n                continue;\n            }\n            int u = edge[0];\n            int v = edge[1];\n            int cost = edge[2];\n            int p1 = find(u, parent);\n            int p2 = find(v, parent);\n            if(p1 != p2) {\n                union(p1, p2, parent);\n                ans += cost;\n                size += 1;\n            }\n        }\n\n        return (size == n - 1) ? ans : Integer.MAX_VALUE; \n    }\n\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        int originalEdges[][] = new int[edges.length][3];\n        for(int i = 0; i < edges.length; i++) {\n            originalEdges[i][0] = edges[i][0];\n            originalEdges[i][1] = edges[i][1];\n            originalEdges[i][2] = edges[i][2];\n        }\n        List<List<Integer>> result = new ArrayList<>();\n        List<Integer> criticalEdges = new ArrayList<>();\n        List<Integer> pseudoCriticalEdges = new ArrayList<>();\n        Arrays.sort(edges, (a, b) -> a[2] - b[2]);\n        int originalCost = mst(n, edges, null, null);\n        for(int i = 0; i < originalEdges.length; i++) {\n            int excludedCost = mst(n, edges, null, originalEdges[i]);\n            int includedCost = mst(n, edges, originalEdges[i], null);\n            if(excludedCost > originalCost) {\n                criticalEdges.add(i);\n            } else if(includedCost == originalCost) {\n                pseudoCriticalEdges.add(i);\n            }\n        }\n        result.add(criticalEdges);\n        result.add(pseudoCriticalEdges);\n        return result;\n    }\n}\n\n```\n```Python []\nclass Solution :\n    def find(self,u,parent):\n        if u == parent[u] : return u\n        return self.find(parent[u], parent)\n\n    def unionDSU(self,u,v,parent) :\n        p1 = self.find(u, parent)\n        p2 = self.find(v, parent)\n        parent[p2] = p1\n\n    def mst(self,n,edges,includeEdge,excludeEdge) :\n\n        parent=[]\n        for i in range(n): \n            parent.append(i);\n        \n        ans = 0\n        count = 0\n\n        if len(includeEdge) != 0 :\n            self.unionDSU(includeEdge[0], includeEdge[1], parent)\n            ans += includeEdge[2]\n            count += 1\n        \n        for edge in edges:\n            u = edge[0];\n            v = edge[1];\n            cost = edge[2];\n\n            if len(excludeEdge) != 0 and excludeEdge[0] == u and excludeEdge[1] == v and excludeEdge[2] == cost :\n                continue\n            \n\n            if len(includeEdge) != 0 and includeEdge[0] == u and includeEdge[1] == v and includeEdge[2] == cost :\n                continue\n            \n\n            p1 = self.find(u, parent)\n            p2 = self.find(v, parent)\n\n            if p1 != p2:\n                self.unionDSU(p1, p2, parent)\n                ans += cost\n                count += 1\n            \n        \n        return  ans if count==n-1 else float(\'inf\')\n    \n    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        \n        originalEdges=[]\n        for edge in edges : \n            originalEdge=[edge[0], edge[1], edge[2]]\n            originalEdges.append(originalEdge)\n        \n\n        result=[]\n        criticalEdges=[]\n        pseudoCriticalEdges=[]\n\n        \n        edges=sorted(edges, key = lambda x: x[2])\n\n        emptyVector=[]\n        originalCost = self.mst(n, edges, emptyVector, emptyVector)\n\n        \n        for i in range(len(originalEdges)): \n\n            excludedCost = self.mst(n, edges, emptyVector, originalEdges[i])\n            includedCost = self.mst(n, edges, originalEdges[i], emptyVector)\n\n            if excludedCost > originalCost :\n                criticalEdges.append(i)\n            elif includedCost == originalCost : \n                pseudoCriticalEdges.append(i)\n            \n        \n        result.append(criticalEdges)\n        result.append(pseudoCriticalEdges)\n        return result\n\n```\n```C++ []\nclass Solution {\npublic:\n    int find(int u, vector<int>& parent) {\n        if(u == parent[u]) return u;\n        return find(parent[u], parent);\n    }\n\n    void unionDSU(int u, int v, vector<int>& parent) {\n        int p1 = find(u, parent);\n        int p2 = find(v, parent);\n        parent[p2] = p1;\n    }\n\n    int mst(int n, vector<vector<int>>& edges, vector<int>& includeEdge, vector<int>& excludeEdge) {\n\n        vector<int> parent;\n        for(int i = 0; i < n; i++) {\n            parent.push_back(i);\n        }\n        int ans = 0;\n        int count = 0;\n\n        if(includeEdge.size() != 0) {\n            unionDSU(includeEdge[0], includeEdge[1], parent);\n            ans += includeEdge[2];\n            count += 1;\n        }\n        for(auto edge : edges) {\n            int u = edge[0];\n            int v = edge[1];\n            int cost = edge[2];\n\n            if(excludeEdge.size() != 0 && excludeEdge[0] == u && excludeEdge[1] == v && excludeEdge[2] == cost) {\n                continue;\n            }\n\n            if(includeEdge.size() != 0 && includeEdge[0] == u && includeEdge[1] == v && includeEdge[2] == cost) {\n                continue;\n            }\n\n            int p1 = find(u, parent);\n            int p2 = find(v, parent);\n\n            if(p1 != p2) {\n                unionDSU(p1, p2, parent);\n                ans += cost;\n                count += 1;\n            }\n        }\n        return count == n - 1 ? ans : INT_MAX;\n    }\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> originalEdges;\n        for(auto edge : edges) {\n            vector<int> originalEdge{edge[0], edge[1], edge[2]};\n            originalEdges.push_back(originalEdge);\n        }\n\n        vector<vector<int>> result;\n        vector<int> criticalEdges;\n        vector<int> pseudoCriticalEdges;\n\n        sort(edges.begin(), edges.end(), \n        [](const vector<int> &x, const vector<int> &y) { return x[2] < y[2]; });\n\n        vector<int> emptyVector;\n        int originalCost = mst(n, edges, emptyVector, emptyVector);\n\n        for(int i = 0; i < originalEdges.size(); i++) {\n            int excludedCost = mst(n, edges, emptyVector, originalEdges[i]);\n            int includedCost = mst(n, edges, originalEdges[i], emptyVector);\n            if(excludedCost > originalCost) {\n                criticalEdges.push_back(i);\n            } else if(includedCost == originalCost) {\n                pseudoCriticalEdges.push_back(i);\n            }\n        }\n        result.push_back(criticalEdges);\n        result.push_back(pseudoCriticalEdges);\n        return result;\n    }\n};\n```\n
['C++', 'Java', 'Python3']