Hardest problem I solved
Intuition\nThe problem asks to find the critical and pseudo-critical edges in a Minimum Spanning Tree (MST). Critical edges are those whose removal increases th
# Intuition\nThe problem asks to find the critical and pseudo-critical edges in a Minimum Spanning Tree (MST). Critical edges are those whose removal increases the weight of the MST, while pseudo-critical edges are those that can be included in some valid MST without changing the weight.\n\nThe core idea is that for each edge, we can:\n\n1. Exclude it and check if the MST weight increases.\n2. Force its inclusion and check if it results in the same MST weight.\n\n# Approach\n1. We need indices so we will store them seperately before sorting.\n2. Sort the edges to apply kruskal\'s.\n2. Find the base MST for weight comparison.\n3. Iterate in each edge exclude it and then find MST to get the critical edge.\n4. Then forcefully include the same edge to get if it is a pseudo critical edge.\n5. Finally return the ans.\n\n# Complexity\n- Time complexity: O(e^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(e+n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Disjoint{\n    public:\n    vector<int> rank, parent;\n\n    Disjoint(int n){\n        rank.resize(n+1, 0);\n        parent.resize(n+1);\n        for(int i=0;i<=n;i++){\n            parent[i] = i;\n        }\n    }\n\n    int findparent(int u){\n        if(u == parent[u]){\n            return u;\n        }\n        return parent[u] = findparent(parent[u]);\n    }\n\n    void Union(int u, int v){\n        int top_u = findparent(u);\n        int top_v = findparent(v);\n\n        if(top_u==top_v){\n            return;\n        }\n\n        if(rank[top_v]>rank[top_u]){\n            parent[top_u] = top_v; \n        }\n        else if(rank[top_v]<rank[top_u]){\n            parent[top_v] = top_u;\n        }\n        else{\n            parent[top_v] = top_u;\n            rank[top_u]++;\n        }\n    }\n};\n\nclass Solution {\nprivate:\n    int findMST(int n, vector<vector<int>>& edges, int e, int j, bool isinclude){\n        Disjoint s(n);\n        int tw = 0;  //Total weight of spanning Tree\n        int ecnt = 0; //Calculate the edge count of tree to see if it results in a single component or not\n        if(isinclude){\n            s.Union(edges[j][0], edges[j][1]);\n            tw+=edges[j][2];\n            ecnt++;\n        }\n        for(int i=0;i<e;i++){\n            if(i!=j && s.findparent(edges[i][0]) != s.findparent(edges[i][1])){\n                tw+=edges[i][2];\n                s.Union(edges[i][0],edges[i][1]);\n                ecnt++;\n            }\n        }\n        \n        return ecnt==n-1 ? tw:INT_MAX;\n    }\n\n    public:\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n\n        //Find starting MST\n        int e = edges.size();\n        for(int i=0;i<e;i++){\n            edges[i].push_back(i);\n        }\n        sort(edges.begin(), edges.end(), cmp);\n        int MST_weight = findMST(n, edges, e, -1, false);\n\n        //Excluding and including each edge now.\n        vector<int> ce;\n        vector<int> pce;\n        for(int i=0;i<e;i++){\n            int curr_weight = findMST(n, edges, e, i, false); //exclude\n            if(curr_weight>MST_weight){\n                ce.push_back(edges[i][3]);\n            }\n            else{\n                curr_weight = findMST(n, edges, e, i, true); //include\n                if(curr_weight==MST_weight){\n                    pce.push_back(edges[i][3]);\n                }\n            }\n\n\n        }\n\n        return {ce, pce};\n    }\n\n    bool static cmp(vector<int>& a, vector<int>& b){\n        return a[2]<b[2];\n    }\n};\n```
['Union Find', 'Sorting', 'Minimum Spanning Tree', 'C++']