C++ | Clean Implementation | Clear Short Explanation | NO CRAP SOLUTION
Starting\n###### You must first sort the given list of edges on the basis of weight. I did so by making first element in vector as weight, and added the index o
# Starting\n###### You must first sort the given list of edges on the basis of weight. I did so by making first element in vector as weight, and added the index of the edge at end of each vector.\n``` C++ []\n//GENERATE SORTED LIST\n        for(int i=0;i<edges.size();i++){\n            int u=edges[i][0],v=edges[i][1],w=edges[i][2];\n            edges[i][0]=w,\n            edges[i][1]=u,\n            edges[i][2]=v,\n            edges[i].push_back(i);\n        }\n        sort(begin(edges),end(edges));\n\n```\n# Approach\n<!-- Describe your approach to solving the problem. -->\n###### Basically, It is literally just a Kruskal question. Find original MST\'s cost for graph. Then for each edge run Kruskal\'s Algo.\n1) You must either **skip edge** and check if the cost of tree increases. If tree cannot form or cost increases then <b>edge is critical</b>\n2) You must make **sure to include the edge** and check if cost of tree is same as original Kruskal Tree\'s cost. If yes then edge can replace another edge and is a <b>pseudo-critical edge.</b>\n# Complexity\n- Time complexity: $O(E^2V)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(V)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n``` C++ []\nclass Solution {\npublic:\n    int components,n;\n    vector<int> parent;\n    vector<int> size;\n    int find_parent(int u){\n        int org=u;\n        //find parent of u, store in u\n        while(parent[u]!=u){\n            u=parent[u];\n        }\n        //Path compression - Optional\n        while(parent[org]!=u){\n            int next=parent[org];\n            parent[org]=u;\n            org=next;\n        }\n        return u;\n    }\n    void union_func(int u,int v){\n        int u_parent=find_parent(u);\n        int v_parent=find_parent(v);\n        if(u==v) return;\n        if(size[u_parent]>size[v_parent]){\n            parent[v_parent]=u_parent;\n            size[u_parent]+=size[v_parent];\n        }\n        else {\n            parent[u_parent]=v_parent;\n            size[v_parent]+=size[u_parent];\n        }\n        components--;\n    }\n    int Kruskal_MST(vector<vector<int>>&edges,int skip,int include){\n        components=n;\n        parent.resize(n),size.resize(n);\n        for(int i=0;i<n;i++) parent[i]=i,size[i]=1;\n\n        int mst_weight=0;\n        if(include!=-1){\n            mst_weight+=edges[include][0];\n            union_func(edges[include][1],edges[include][2]);\n        }\n        for(int i=0;i<edges.size();i++){\n            if(i==skip) continue;\n            int w=edges[i][0],u=edges[i][1],v=edges[i][2],ind=edges[i][3];\n            if(find_parent(u)==find_parent(v)) continue;\n            else {\n                mst_weight+=w;\n                union_func(u,v);\n            }\n        }\n        return components!=1?INT_MAX:mst_weight;\n    }\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> ans(2,vector<int>());\n        this->n=n;\n        //GENERATE SORTED LIST\n        for(int i=0;i<edges.size();i++){\n            int u=edges[i][0],v=edges[i][1],w=edges[i][2];\n            edges[i][0]=w,\n            edges[i][1]=u,\n            edges[i][2]=v,\n            edges[i].push_back(i);\n        }\n        sort(begin(edges),end(edges));\n\n        //FIND TRUE KRUSKAL WT\n        int krusk_min_weight=Kruskal_MST(edges,-1,-1);\n\n        //TEST ALL EDGES\n        for(int i=0;i<edges.size();i++) {\n            //critical - IF SKIP EDGE, WT INCREASE\n            //pscritical - IF INCLUDED EDGE, WT SAME\n            int skip_edge_wt=Kruskal_MST(edges,i,-1); \n            int include_edge_wt=Kruskal_MST(edges,-1,i);\n            if(skip_edge_wt>krusk_min_weight)\n                ans[0].push_back(edges[i][3]);\n            else if(include_edge_wt==krusk_min_weight)\n                ans[1].push_back(edges[i][3]);\n        }\n        return ans;\n    }\n};\n```
['Union Find', 'Graph', 'Sorting', 'Minimum Spanning Tree', 'Strongly Connected Component', 'C++']