[C++] Detailed Explanation | Time Complexity Analysis | Solution using Krushkal's Algorithm
Intuition\n Describe your first thoughts on how to solve this problem. \nFrom the problem description the followings are evident:\n1. We are dealing with minimu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFrom the ***problem description*** the followings are **evident**:\n1. We are dealing with minimum spanning tree (MST).\n2. Critical edges are present in every possible MSTs.\n3. Pseudo critical edges are present in only some of the MSTs. (But they must be present in atlest one of the MSTs)\n\n**Mental Map:**\n1. We need to return the indices of this edges, so we will need to store this information in our edgeList datastructure.\n2. We need a function/methed to find MST (We will use krushkal\'s Algorithm)\n\n\n# Approach\n1. Find the "mst" of the given graph.\n2. Now, one by one skipping an edge find the "curr_mst" of the graph.\n-- (Here, Skipping means, not allowing that edge to be part of the MST)\n3. If "curr_mst" > "mst" then we can certainly claim that the skipped edge belongs to critical edge.\n4. If "curr_mst" == "mst" then this might be a pseudoCritical edge.\n-- But why "might be" ?? \n    Because, it may happen, this edge will never be part of our MST\n-- e.g : n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]\n    Here, edges[5] = [1,4,6] is never part of a MST (the way are doing the processing, i.e: skipping edge)\n5. So, to verify this, we will force this edge to be part of our MST, and calculate the "curr_mst" again.\n-- If "curr_mst" == "mst" (after recalculation), We can certainly say that this, edge belongs to pseudoCritical edge.\n\n# Complexity\n- Time complexity: \n-- O(E^2 * \u03B1(V)), \u03B1: Ackermann Function, E: Edge Count, V: Node Count\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n-- O(V + E)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass DSU {\nprivate:\n    int sz;\n    vector<int> root, rank;\npublic:\n    DSU(int sz){\n        this->sz = sz;\n        root.resize(sz);\n        rank.resize(sz);\n        for(int i = 0; i < sz; i++){\n            root[i] = i;\n            rank[i] = 1;\n        }\n    }\n    \n    int find(int x){\n        if(root[x] == x) return x;\n        return root[x] = find(root[x]);\n    }\n    \n    bool unionSet(int x, int y){\n        int rootX = find(x);\n        int rootY = find(y);\n        if(rootX == rootY)\n            return false;\n        if(rank[rootX] > rank[rootY])\n            root[rootY] = rootX;\n        else if(rank[rootX] < rank[rootY])\n            root[rootX] = rootY;\n        else{\n            root[rootY] = rootX;\n            rank[rootX]++;\n        }\n        return true;\n    }\n\n    void reset() {\n        for(int i = 0; i < sz; i++){\n            root[i] = i;\n            rank[i] = 1;\n        }\n    }\n};\n\nclass Solution {\nprivate:\n    int N;\n    DSU *dsu;\n    int edgeCount;\n    vector<vector<int>> myEdges;\n    int findMSTwithCondition(int avoidMe, bool alreadyPickedOne) {  \n        // If avoidMe == -1 then find MST for the given edgeList\n        // If alreadyPickedOne == true, then our dsu already has that information recorded\n        // This, function will try to find the MST with above two condition\n        // If Spanning Tree is not possible it will return INT_MAX\n        int ans = 0;\n        int totalOp = 0;\n        if (alreadyPickedOne) totalOp++;\n        for (int i = 0; i < edgeCount; i++) {                        // O(edgeCount * \u03B1(V))\n            if (totalOp == N - 1) break;\n            if (myEdges[i][3] == avoidMe) continue;\n            if (dsu->unionSet(myEdges[i][1], myEdges[i][2])) {\n                ans += myEdges[i][0];\n                totalOp++;\n            }\n        }\n        // Reset the DSU\n        dsu->reset();\n        return totalOp == N - 1 ? ans : INT_MAX;\n    }\npublic:\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        /* Approach:\n            1. Krushkal Algorithm -- T.C: O(E^2 * \u03B1(V)), S.C: O(E); V: No. of nodes(n), E: no of edges\n                -- Intuition:\n                    -- Find the "mst" of the given graph\n                    -- Now, find the "curr_mst" if a particular edge is not selected\n                    -- If "curr_mst" > "mst" then edge we skipped belongs to critical edge\n                    -- If "curr_mst" == "mst" then this edge might be a pseudoCritical edge\n                        -- But why "might be" ?? Because, it may happen that this edge will never be part of our MST\n                        -- e.g : n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]\n                            Here, edges[5] = [1,4,6] is never part of a MST (the way are doing the processing, i.e: skipping edge)\n                        So, to verify this, we will force this edge to be part of our MST, and calculate the "curr_mst" again\n                        If "curr_mst" == "mst" then with certainty we can say this edge belongs to pseudoCritical edge\n        */\n\n        // Approach 1 -- Krushkal\n        N = n;\n        edgeCount = edges.size();\n        myEdges.clear();\n        myEdges.assign(edgeCount, {});\n\n        // Insert index to the edgeList\n        for (int i = 0; i < edgeCount; i++) {\n            myEdges[i].push_back(edges[i][2]);\n            myEdges[i].push_back(edges[i][0]);\n            myEdges[i].push_back(edges[i][1]);\n            myEdges[i].push_back(i);\n        }\n        // Sort myEdges based on weight                             // T.C: O(E log E)\n        sort(myEdges.begin(), myEdges.end(), [](auto const &v1, auto const &v2) ->bool {return v1[0] < v2[0];});\n        // Have a new DSU to find the MST of the tree\n        dsu = new DSU(N);                     // O(n)\n        int mst = findMSTwithCondition(-1, false);\n        if (mst == INT_MAX) {\n            // Spanning Tree Not possible for this graph\n            delete dsu;\n            return {};\n        }\n\n        vector<int> critical;\n        vector<int> pseudoCritical;\n        for (int i = 0; i < edgeCount; i++) {                       // T.C: O(edgeCount^2 * \u03B1(V))\n            // Find MST by not taking ith edge\n            int curr_mst = findMSTwithCondition(i, false);\n            if (curr_mst > mst)                 // Definitely a critical edge\n                critical.push_back(i);\n            else if (curr_mst == mst) {         // Might be a pseudoCritical edge\n                // Let\'s calculate MST by taking this edge\n                curr_mst = edges[i][2];\n                dsu->unionSet(edges[i][0], edges[i][1]);\n                curr_mst += findMSTwithCondition(-1, true);\n                if (curr_mst == mst) pseudoCritical.push_back(i);   // We are sure this is a pseudoCritical edge\n            }\n        }\n\n        delete dsu;\n        return {critical, pseudoCritical};\n    }\n};\n```
['Union Find', 'Graph', 'Minimum Spanning Tree', 'C++']