Explained With Images and Steps | Hard to Understand Made Easy 🏆
Intuition\nThere are two algorithms to find MST.\n- Prim\'s Algorithm\n- Kruskal\'s Algorithm\n\nWe will be using Kruskal\'s algorithm in this case. Those of yo
# Intuition\nThere are two algorithms to find MST.\n- Prim\'s Algorithm\n- Kruskal\'s Algorithm\n\nWe will be using Kruskal\'s algorithm in this case. Those of you who don\'t know, Kruskal\'s algorithm is actually a modification of the union find algorithm. You need to understand the Union Find algorithm properly to understand Kruskal\'s algorithm.\n\nWe will divide this solution to steps:\n\n## Step 1 (Create a new array to store the edges and corresponding indices):\n\nTo calculate MST, we are concerned with minimum weights. Therefore, we will need to sort the array. But this will change the original index of the array. So, create a new array and store exisiting values along with their indices.\n\n``` java []\nint m = edges.length;\nint[][] newEdges = new int[m][4];\nfor(int i=0; i<m; 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\n## Step 2 (Sort the edges array):\n\nWe sort the array in ascending order based on their weights.\nThe array elements are:\n```\nindex:       0    1     2       3\nnewEdges = {from, to, weight, index}\n```\n``` java []\nArrays.sort(newEdges, (a, b) -> a[2]-b[2]);\n```\n\n## Step 3 (Write a class for UnionFind):\n\nWe will need union find algorithm. So, let\'s write a class for it.\n\n``` java []\nclass UnionFind {\n    int[] parent;\n    int[] rank;\n    int maxSize;\n    public UnionFind(int n) {\n        parent = new int[n];\n        rank = new int[n];\n        maxSize = 1;\n        for(int i=0; i<n; i++) {\n            parent[i] = i;\n            rank[i] = 1;\n        }\n    }\n    public int find(int a) {\n        while(parent[a]!=a) {\n            parent[a] = parent[parent[a]];\n            a = parent[a];\n        }\n        return a;\n    }\n    public boolean makeUnion(int a, int b) {\n        int parA = find(a), parB = find(b);\n        if(parA != parB) {\n            if(rank[parA] < rank[parB]) {\n                parent[parA] = parB;\n                rank[parB] += rank[parA];\n                maxSize = Math.max(maxSize, rank[parB]);\n            }\n            else {\n                parent[parB] = parA;\n                rank[parA] += rank[parB];\n                maxSize = Math.max(maxSize, rank[parA]);\n            }\n            return true;\n        }\n        return false;\n    }\n}\n```\n\n## Step 4 (Calculate the Weight of Actual MST):\n\nThe visualization how Kruskal\'s algorithm works is shown below.\n\n<img style="background: #F3FDE8" src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/5c/MST_kruskal_en.gif/600px-MST_kruskal_en.gif" />\n\nReference: [wikimedia.org](https://commons.wikimedia.org/wiki/File:MST_kruskal_en.gif)\n\nUse the union find approach and calculate the actual Minimum Spanning Tree.\n\nUsing the union find algorithm, calculate the weight of the standard MST.\n\n``` java []\nint weight = 0;\nUnionFind ufMST = new UnionFind(n);\nfor(int[] edge : newEdges) {\n    if(ufMST.makeUnion(edge[0], edge[1])) {\n        weight += edge[2];\n    }\n}\n```\n\n## Step 5 (Find the Critical and Pseudo Critical Edges):\n\nThe above part was easy. But from now it gets a bit tricky. We need to properly understand what a critical and pseudo path is.\n\n- **Critical Path**:\n\nLet\'s suppose we delete the edge between node 0 and 1.\n\n![Untitled presentation.png](https://assets.leetcode.com/users/images/60e19e15-8e5a-4c60-a5dc-53473e8796ea_1692456577.7516568.png)\n\nWe can see from the right side of the image that we can form these trees. All of them has `weight > actual weight`. So, they are not a spanning tree. This happened because we removed the edge $<0,1>$ from the edges. So, edge $<0, 1>$ is a critical edge.\n\nSimilarly, if we remove edge $<1, 2>$, we will get spanning tree having more weight than actual. So, this is also a critical path.\n\n**Remember, Spanning tree is a connected graph**. If removing an edge disconnects the graph, it will not be a spanning tree. Hence, that edge is critical.\nSo, two conditions for an edge to be critical. Without that edge:\n1. Calculated weight becomes greater than actual MST weight. \n2. The graph may become disconnected.\n\n- **Pseudo Path**:\nThis could be tricky to understand. We can forcefully include an edge in the spanning tree union to see if the total weight becomes equal to the actual MST weight. If so, then this edge that we\'ve forcefully included is a pseudo edge.\n\n![image.png](https://assets.leetcode.com/users/images/4313ba64-cc33-4c40-a0bf-1dcca8be4f19_1692457336.7808957.png)\n\nFrom the above image we can see that edges $<2, 2>, <5, 3>, <4, 3>$ \nand $<3, 2>$ are pseudo edges. Because, we can forcefully include them in the spanning tree and find the weight to be equal.\n\n**Remember, Minimum Spanning Tree is not Unique!!**\n\n``` java []\nfor(int i=0; i<m; i++) {\n    UnionFind ufCritical = new UnionFind(n);\n    int ignoreWeight = 0;\n    // ignoring edge i\n    // Union all the edges except i\n    for(int j=0; j<m; j++) {\n        if(i!=j && ufCritical.makeUnion(newEdges[j][0], newEdges[j][1])) {\n            ignoreWeight += newEdges[j][2];\n        }\n    }\n    // if not all vertices are in the union or, weight has increased\n    // that means we cannot form MST without edge i.\n    // So, it is a critical edge\n    if(ufCritical.maxSize < n || ignoreWeight > weight) {\n        // add it\'s original index\n        result.get(0).add(newEdges[i][3]);\n    }\n    else {\n        UnionFind ufForce = new UnionFind(n);\n        // we don\'t know if edge i was in our original MST\n        // but we will forcefully include it\n        ufForce.makeUnion(newEdges[i][0], newEdges[i][1]);\n        int forceWeight = newEdges[i][2]; // cause we have already taken edge i\n        for(int j=0; j<m; j++) {\n            if(i!=j && ufForce.makeUnion(newEdges[j][0], newEdges[j][1])) {\n                forceWeight += newEdges[j][2];\n            }\n        }\n        if(forceWeight == weight) {\n            // if the weight after forcing an edge is equal to the original MST weight\n            // that means this is a pseudo edge.\n            result.get(1).add(newEdges[i][3]);\n        }\n    }\n}\n```\n\n\n# Complexity\n- Time complexity: $O(V E)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(V+E) = O(N)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n``` java []\nclass UnionFind {\n    int[] parent;\n    int[] rank;\n    int maxSize;\n    public UnionFind(int n) {\n        parent = new int[n];\n        rank = new int[n];\n        maxSize = 1;\n        for(int i=0; i<n; i++) {\n            parent[i] = i;\n            rank[i] = 1;\n        }\n    }\n    public int find(int a) {\n        while(parent[a]!=a) {\n            parent[a] = parent[parent[a]];\n            a = parent[a];\n        }\n        return a;\n    }\n    public boolean makeUnion(int a, int b) {\n        int parA = find(a), parB = find(b);\n        if(parA != parB) {\n            if(rank[parA] < rank[parB]) {\n                parent[parA] = parB;\n                rank[parB] += rank[parA];\n                maxSize = Math.max(maxSize, rank[parB]);\n            }\n            else {\n                parent[parB] = parA;\n                rank[parA] += rank[parB];\n                maxSize = Math.max(maxSize, rank[parA]);\n            }\n            return true;\n        }\n        return false;\n    }\n}\nclass Solution {\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        int m = edges.length;\n        int[][] newEdges = new int[m][4];\n        for(int i=0; i<m; 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, (a, b)->a[2]-b[2]);\n\n        int weight = 0;\n        UnionFind ufMST = new UnionFind(n);\n        for(int[] edge : newEdges) {\n            if(ufMST.makeUnion(edge[0], edge[1])) {\n                weight += edge[2];\n            }\n        }\n\n        List<List<Integer>> result = new ArrayList<>();\n        // critical edges result.get(0)\n        result.add(new ArrayList<>());\n        // pseudo critical edges result.get(1)\n        result.add(new ArrayList<>());\n\n        for(int i=0; i<m; i++) {\n            UnionFind ufCritical = new UnionFind(n);\n            int ignoreWeight = 0;\n            // ignoring edge i\n            // Union all the edges except i\n            for(int j=0; j<m; j++) {\n                if(i!=j && ufCritical.makeUnion(newEdges[j][0], newEdges[j][1])) {\n                    ignoreWeight += newEdges[j][2];\n                }\n            }\n            // if not all vertices are in the union or, weight has increased\n            // that means we cannot form MST without edge i.\n            // So, it is a critical edge\n            if(ufCritical.maxSize < n || ignoreWeight > weight) {\n                // add it\'s original index\n                result.get(0).add(newEdges[i][3]);\n            }\n            else {\n                UnionFind ufForce = new UnionFind(n);\n                // we don\'t know if edge i was in our original MST\n                // but we will forcefully include it\n                ufForce.makeUnion(newEdges[i][0], newEdges[i][1]);\n                int forceWeight = newEdges[i][2]; // cause we have already taken edge i\n                for(int j=0; j<m; j++) {\n                    if(i!=j && ufForce.makeUnion(newEdges[j][0], newEdges[j][1])) {\n                        forceWeight += newEdges[j][2];\n                    }\n                }\n                if(forceWeight == weight) {\n                    // if the weight after forcing an edge is equal to the original MST weight\n                    // that means this is a pseudo edge.\n                    result.get(1).add(newEdges[i][3]);\n                }\n            }\n        }\n        return result;\n    }\n}\n```
['Union Find', 'Java']