👌 Simple and Clear C++ Solution💡
Prerequisite\n- Union-find data structure\n- Kruskal\'s algorithm\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nEdge Type | Rela
# Prerequisite\n- Union-find data structure\n- Kruskal\'s algorithm\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nEdge Type | Relation b/w MST<sub>force</sub>(MST weight with edge forced) and MST<sub>ignore</sub>(MST weight edge ingnored)\n--- | ---\nCritical | MST<sub>force</sub> < MST<sub>ignore</sub>\nPseudo-Critical | MST<sub>force</sub> = MST<sub>ignore</sub>\nNon-Critical | MST<sub>force</sub> > MST<sub>ignore</sub>\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse modified Kruskal\'s Algorithm to find MST<sub>force</sub> and MST<sub>ignore</sub> for each edge and build up the answer according to the above intuition.\n\n# Complexity\n- Time complexity: $$O(mlogm + m^2)$$, where $$m$$ is the number of edges.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(m+n)$$, where $$n$$ is the number of nodes.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int find(int x,vector<int> &par) {\n        if(par[x]==x) {\n            return x;\n        }\n        return par[x]=find(par[x],par);\n    }\n    int MST(int n,int m,bool taken,int ind,vector<vector<int>> &e) {\n        int res=0,cnt=0;\n        vector<int> par(n);\n        for(int i=0;i<n;i++) {\n            par[i]=i;\n        }\n        if(taken) {\n            par[e[ind][3]]=e[ind][2];\n            res+=e[ind][0];\n            cnt++;\n        }\n        for(int i=0;i<m;i++) {\n            if(i==ind) {\n                continue;\n            }\n            int pu=find(e[i][2],par),pv=find(e[i][3],par);\n            if(pu!=pv) {\n                par[pv]=pu;\n                res+=e[i][0];\n                cnt++;\n            }\n        }\n        return (cnt==n-1?res:INT_MAX);\n    }\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n,vector<vector<int>> &edges) {\n        int m=edges.size();\n        vector<vector<int>> e(m);\n        for(int i=0;i<m;i++) {\n            e[i]={edges[i][2],i,edges[i][0],edges[i][1]};\n        }\n        sort(e.begin(),e.end());\n        vector<vector<int>> ans(2);\n        for(int i=0;i<m;i++) {\n            int takenWeight=MST(n,m,true,i,e),notTakenWeight=MST(n,m,false,i,e);\n            if(notTakenWeight>takenWeight) {\n                ans[0].push_back(e[i][1]);\n            }\n            else if(notTakenWeight==takenWeight) {\n                ans[1].push_back(e[i][1]);\n            }\n        }\n        return ans;\n    }\n};\n```
['Union Find', 'Graph', 'Sorting', 'Minimum Spanning Tree', 'C++']