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. struct Graph {
  14.     vector<vector<pair<int, int>>> adj;
  15.     Graph(int n) {
  16.         adj.resize(n);
  17.     }
  18.     void add(int x, int y, int w) {
  19.         adj[x].push_back({y, w});
  20.         adj[y].push_back({x, w});
  21.     }
  22.     int weight(int x, int y) {
  23.         for(auto& nxt : adj[x]) {
  24.             if(nxt.first == y) return nxt.second;
  25.         }
  26.         return -1;
  27.     }
  28. };
  29. struct Dsu{
  30.     vector<int> par;
  31.     vector<int> siz;
  32.     Dsu(int n) {
  33.         par.resize(n + 1);
  34.         siz.resize(n + 1, 1);
  35.         for(int i = 0; i <= n; i++) {
  36.             par[i] = i;
  37.         }
  38.     }
  39.     int findPar(int x) {
  40.         if (par[x] != x)
  41.             par[x] = findPar(par[x]);
  42.         return par[x];
  43.     }
  44.     void unite(int x, int y) {
  45.         int xP = findPar(x);
  46.         int yP = findPar(y); 
  47.         if(xP == yP) return;
  48.         if(siz[xP] > siz[yP]) {
  49.             par[yP] = xP;
  50.             siz[xP] += siz[yP];
  51.         }else {
  52.             par[xP] = yP;
  53.             siz[yP] += siz[xP];
  54.         }
  55.     }
  56. };
  57. void kruskal(Graph g) {
  58.     int V = g.adj.size();
  59.     Dsu dsu(V);
  60.     vector<tuple<int, int, int>> edges; // (weight, u, v)
  61.  
  62.     for(int u = 0; u < V; ++u) {
  63.         for(auto& [v, w] : g.adj[u]) {
  64.             if(u < v) { // to avoid duplicate edges in undirected graph
  65.                 edges.push_back({w, u, v});
  66.             }
  67.         }
  68.     }
  69.  
  70.     sort(edges.begin(), edges.end());
  71.  
  72.     int mst_cost = 0;
  73.     vector<pair<int, int>> mst_edges;
  74.  
  75.     for(auto& [w, u, v] : edges) {
  76.         if(dsu.findPar(u) != dsu.findPar(v)) {
  77.             dsu.unite(u, v);
  78.             mst_edges.push_back({u, v});
  79.             mst_cost += w;
  80.         }
  81.     }
  82.  
  83.     for(auto& [u, v] : mst_edges) {
  84.         cout << u << " -- " << v << endl;
  85.     }
  86.     cout << "MST cost: " << mst_cost << endl;
  87. }
  88.  
  89. signed main() {
  90.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  91.     freopen("Error.txt", "w", stderr);
  92.  
  93.     int n = 5;
  94.     Graph g(n);
  95.  
  96.     g.add(0, 2, 1);
  97.     g.add(0, 1, 2);
  98.     g.add(1, 2, 1);
  99.     g.add(2, 4, 2);
  100.     g.add(4, 3, 1);
  101.     g.add(2, 3, 2);
  102.  
  103.     kruskal(g);
  104. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 -- 2
1 -- 2
3 -- 4
2 -- 3
MST cost: 5
https://ideone.com/n3hUNi
Kruskal
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!