Prim's Solution || C++ ||
IntuitionThis isn't the most efficient solution; Kruskal's algorithm is definitely much more efficient. However, I deliberately forced myself to adapt Prim's al
# Intuition
This isn't the most efficient solution; Kruskal's algorithm is definitely much more efficient. However, I deliberately forced myself to adapt Prim's algorithm to solve this problem.
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->
Explanation added to the code 
# Complexity
- Time complexity: $$O(E^2. Log(V))$$ who cares!
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
    unordered_map<int, vector<pair<int, int>>> graph;
public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
        
        // building the graph
        for (const vector<int>& edge: edges) {
            graph[edge[0]].emplace_back(edge[1], edge[2]);
            graph[edge[1]].emplace_back(edge[0], edge[2]);
        }
        
        // getting the MST cost, by default all edges included
        int MSTCost = getMSTCost(n);

        // setting up our final result vector
        vector<vector<int>> result(2, vector<int>());

        for (int i=0; i<edges.size(); ++i){
            // calculating cost by excluding the edge
            int newCost = getMSTCost(n, false, edges[i][0], edges[i][1]);

            if (newCost == MSTCost) {
                // make sure it's acutally used in the MST 
                if (getMSTCost(n, true, edges[i][0], edges[i][1]) > MSTCost) continue; 
                result[1].push_back(i);
            }
            //if (newCost > MSTCost || newCost < MSTCost) second case possible when it separates the graph
            else { // into two components
                result[0].push_back(i);
            }
        }
        return result;
    }

    // getMSTCost(n) --> include all the edges
    // getMSTCost(n, false a, b) --> exclude a-b edge
    // getMSTCost(n, true, a, b) --> forcibly include a-b edge
    int getMSTCost(int n, bool include_edge=false, int a=-1, int b=-1) {
        // (cost, dest)
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
        vector<bool> visited(n, false);
        int cost = 0;

        if (include_edge) { // we will explore both nodes, adding their path cost to the total cost
            for (const auto& [n1, w1]: graph[a]) {
                if (n1 == b) {cost += w1; continue;}
                minHeap.push({w1, n1});
            }

            for (const auto& [n1, w1]: graph[b]) {
                if (n1 == a) continue; // we added the cost before, we just skip it
                minHeap.push({w1, n1});
            }

            visited[a] = true;
            visited[b] = true;
        }
        else { // in normal scenario start from the zero node
            for (const auto& [n1, w1]: graph[0]) {
                if ((a == n1 && b == 0 ) || (a == 0 && b == n1)) continue;
                minHeap.push({w1, n1});
            }

            visited[0] = true;
        }
        
        while(!minHeap.empty()){
            auto [w1, n1] = minHeap.top();
            minHeap.pop();

            if (visited[n1]) continue;
            visited[n1] = true;
            cost += w1;

            for(const auto& [n2, w2]: graph[n1]) {
                if (visited[n2]) continue;
                // we skip in exclude or include cases, this when b & a are provided
                if ((n1 == a && n2 == b ) || (n1 == b && n2 == a)) continue;
                minHeap.push({w2, n2});
            }
        }
        return cost;
    }
};

```
['Graph', 'Minimum Spanning Tree', 'C++']