Prim (MST)
O(m log n)Minimum spanning tree grown from a single vertex with a priority queue. Same output as Kruskal; pick Prim when the graph is already in adjacency-list form or when a virtual super-node trick is involved. No DSU needed.
// use it on
Codeforces 1245D: Shichikuji and Power Grid ↗
Building a power station is an edge to a virtual node 0; the answer is the MST of the augmented graph, a classic Prim setup.
// the code
// adj[u] = {{v, w}, ...}; returns MST cost, or -1 if disconnected
long long prim(vector<vector<pair<int, int>>>& adj) {
int n = adj.size();
vector<bool> in(n, false);
priority_queue<pair<long long, int>, vector<pair<long long, int>>,
greater<>> pq;
pq.push({0, 0});
long long cost = 0;
int taken = 0;
while (!pq.empty() && taken < n) {
auto [w, u] = pq.top();
pq.pop();
if (in[u]) continue;
in[u] = true;
taken++;
cost += w;
for (auto [v, wt] : adj[u])
if (!in[v]) pq.push({wt, v});
}
return taken == n ? cost : -1;
}// more spanning trees