fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #ifndef ONLINE_JUDGE
  5. #include "algo/debug.h"
  6. #else
  7. #define debug(...) 42
  8. #endif
  9. const int N = 2e5+10;
  10. #define fr(x, y) for(int i = x; i < y; i++)
  11. vector<int> A;
  12. /*
  13. PRIM-MST(G)
  14. 1    let V be the number of vertices in G
  15. 2    for each u in G.V
  16. 3        key[u] ← ∞
  17. 4        parent[u] ← NIL
  18. 5        inMST[u] ← FALSE
  19. 6    key[0] ← 0
  20.  
  21. 7    Q ← empty min-priority queue
  22. 8    INSERT(Q, (0, 0, NIL))    ▹ (key, vertex, parent)
  23.  
  24. 9    MST ← empty list
  25. 10   total_weight ← 0
  26.  
  27. 11   while Q is not empty
  28. 12       (w, u, p) ← EXTRACT-MIN(Q)
  29. 13       if inMST[u] = TRUE
  30. 14           continue
  31. 15       inMST[u] ← TRUE
  32. 16       if p ≠ NIL
  33. 17           ADD (u, p) to MST
  34. 18           total_weight ← total_weight + w
  35.  
  36. 19       for each (v, weight) in G.Adj[u]
  37. 20           if inMST[v] = FALSE
  38. 21               INSERT(Q, (weight, v, u))
  39.  
  40. 22   for each (u, p) in MST
  41. 23       print u -- p
  42.  
  43. 24   print "MST cost: ", total_weight
  44. */
  45. struct Graph {
  46.     vector<vector<pair<int, int>>> adj;
  47.     Graph(int n) {
  48.         adj.resize(n);
  49.     }
  50.     void add(int x, int y, int w) {
  51.         adj[x].push_back({y, w});
  52.         adj[y].push_back({x, w});
  53.     }
  54.     int weight(int x, int y) {
  55.         for(auto& nxt : adj[x]) {
  56.             if(nxt.first == y) return nxt.second;
  57.         }
  58.         return -1;
  59.     }
  60. };
  61.  
  62. void prims(Graph g) {
  63.     int V = g.adj.size();
  64.     priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
  65.     pq.push({0, 0, -1}); // (wt, node, parent)
  66.  
  67.     vector<int> vis(V + 1, 0);
  68.     int sum = 0;
  69.     vector<pair<int, int>> mst;
  70.  
  71.     while(!pq.empty()) {
  72.         auto [wt, nd, par] = pq.top();
  73.         pq.pop();
  74.         if(vis[nd]) continue;
  75.         vis[nd] = 1;
  76.         if(par != -1) {
  77.             sum += wt;
  78.             mst.push_back({nd, par});
  79.         }
  80.         for(auto& nxt: g.adj[nd]) {
  81.             if(!vis[nxt.first]) {
  82.                 pq.push({nxt.second, nxt.first, nd});
  83.             }
  84.         }
  85.     }
  86.  
  87.     for(auto& edge : mst) {
  88.         cout << edge.first << " -- " << edge.second << endl;
  89.     }
  90.     cout << "MST cost: " << sum << endl;
  91. }
  92.  
  93.  
  94. signed main() {
  95.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  96.     freopen("Error.txt", "w", stderr);
  97.     //freopen("input.txt", "r", stdin);
  98.     //freopen("output.txt", "w", stdout);
  99.     int n = 5;
  100.     Graph g(n);
  101.  
  102.     // {u, v, wt}
  103.     g.add(0, 2, 1);
  104.     g.add(0, 1, 2);
  105.     g.add(1, 2, 1);
  106.     g.add(2, 4, 2);
  107.     g.add(4, 3, 1);
  108.     g.add(2, 3, 2);
  109.  
  110.     prims(g);
  111.  
  112. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 -- 0
1 -- 2
3 -- 2
4 -- 3
MST cost: 5
https://ideone.com/5LdcPd
Prim's Algorithm (priority queue)
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!