Using Prim's Algorithm
All solution given (In solution section) uses Kruskal\'s algorithm.\nHere is my code which uses Prim\'s Algorithm.\n# Code\n\nclass Solution {\npublic:\n    int
All solution given (In solution section) uses Kruskal\'s algorithm.\nHere is my code which uses Prim\'s Algorithm.\n# Code\n```\nclass Solution {\npublic:\n    int mst_cost(vector<vector<pair<int,int>>> &g,int a=-1,int b=-1,int w_ab=0){\n        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;\n        int mst = 0;\n        int num_edge_mst = 0;\n        unordered_set<int> included;         \n        if(a==-1 && b==-1){\n            int min_nbr = -1,w=1e8;\n            for(int i=0;i<g[0].size();i++){\n                auto nbr = g[0][i];\n                if(nbr.second < w){\n                    w = nbr.second;\n                    min_nbr = nbr.first;\n                }\n            }\n            a = 0;\n            b = min_nbr;\n            w_ab = w;\n        }    \n        included.insert(a);\n        included.insert(b);\n        pq.push({-1,a});\n        pq.push({-1,b});\n        mst += w_ab;\n        num_edge_mst += 1;  \n        while(!pq.empty() && num_edge_mst<g.size()-1){      \n            auto f = pq.top();                          \n            pq.pop();                                           \n            if(f.first > 0 && (included.find(f.second)==included.end())){\n                mst += f.first;\n                num_edge_mst += 1;\n                included.insert(f.second);\n            }                               \n            for(auto nbr:g[f.second]){\n                if(included.find(nbr.first) != included.end()) continue;\n                pq.push({nbr.second,nbr.first});\n            }                          \n        }                           \n        return mst;\n    }\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> ans;\n        vector<vector<pair<int,int>>> g(n);\n        for(int i=0;i<edges.size();i++){\n            g[edges[i][0]].push_back({edges[i][1],edges[i][2]});\n            g[edges[i][1]].push_back({edges[i][0],edges[i][2]});\n        }\n        int MST = mst_cost(g);  \n        vector<int> critical;\n        vector<int> p_critical;\n        for(int i=0;i<edges.size();i++){\n            auto e = edges[i];\n            int a = e[0],b = e[1],w = e[2];\n            for(int j=0;j<g[a].size();j++){\n                if(g[a][j].first == b) g[a][j].second = 1001;\n            }\n            for(int j=0;j<g[b].size();j++){\n                if(g[b][j].first == a) g[b][j].second = 1001;\n            }                                       \n            int mst_e = mst_cost(g);                          \n            if(mst_e > MST){\n                critical.push_back(i);\n            }\n            for(int j=0;j<g[a].size();j++){\n                if(g[a][j].first == b) g[a][j].second = w;\n            }\n            for(int j=0;j<g[b].size();j++){\n                if(g[b][j].first == a) g[b][j].second = w;\n            }\n            \n            int mst_e1 = mst_cost(g,a,b,w);             \n            if(mst_e1 == MST){\n                if(mst_e <= MST)\n                p_critical.push_back(i);\n            }\n        }\n        ans.push_back(critical);\n        ans.push_back(p_critical);\n        return ans;\n    }\n};\n```
['Graph', 'Heap (Priority Queue)', 'Minimum Spanning Tree', 'C++']