fork(1) download
copy 
  1. /*
  2.   Copyright 2013 Marek "p2004a" Rusinowski
  3.   Computing MST - Borůvka's algorithm
  4. */
  5. #include <cstdio>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <functional>
  9.  
  10. using namespace std;
  11.  
  12. template <class T, class Compare = less<T> >
  13. class LeftistHeap {
  14.  public:
  15.   class LeftistHeapNode {
  16.    public:
  17.     T value;
  18.     LeftistHeapNode *left, *right;
  19.     int s;
  20.  
  21.     LeftistHeapNode(T vvalue, LeftistHeapNode *lleft, LeftistHeapNode *rright, int ss)
  22.      : value(vvalue), left(lleft), right(rright), s(ss) {}
  23.  
  24.     LeftistHeapNode(const LeftistHeapNode &node) : value(node.value), left(NULL), right(NULL), s(node.s) {
  25.       if (node.left != NULL) left = new LeftistHeapNode(*node.left);
  26.       if (node.right != NULL) right = new LeftistHeapNode(*node.right);
  27.     }
  28.  
  29.     ~LeftistHeapNode() {
  30.       delete left;
  31.       delete right;
  32.     }
  33.   };
  34.  
  35.   LeftistHeapNode *merge(LeftistHeapNode *h1, LeftistHeapNode *h2) {
  36.     if (h1 == NULL) return h2;
  37.     if (h2 == NULL) return h1;
  38.     if (!cmp(h1->value, h2->value)) swap(h1, h2);
  39.     if (h1->left == NULL) h1->left = h2;
  40.     else {
  41.       h1->right = merge(h1->right, h2);
  42.       if (h1->left->s < h1->right->s) swap(h1->left, h1->right);
  43.       h1->s = h1->right->s + 1;
  44.     }
  45.     return h1;
  46.   }
  47.  
  48.  private:
  49.   LeftistHeapNode *root;
  50.   size_t heap_size;
  51.   Compare cmp;
  52.  
  53.  public:
  54.   LeftistHeap() : root(NULL), heap_size(0) {}
  55.  
  56.   LeftistHeap(const LeftistHeap &heap) : root(NULL), heap_size(heap.heap_size) {
  57.     if (heap.root != NULL) root = new LeftistHeapNode(*heap.root);
  58.   }
  59.  
  60.   ~LeftistHeap() {
  61.     delete root;
  62.   }
  63.  
  64.   LeftistHeap &operator=(const LeftistHeap &heap) {
  65.     delete root;
  66.     root = new LeftistHeapNode(*heap.root);
  67.     heap_size = heap.heap_size;
  68.     return *this;
  69.   }
  70.  
  71.   LeftistHeapNode *insert(T value) {
  72.     LeftistHeapNode *node = new LeftistHeapNode(value, NULL, NULL, 0);
  73.     root = merge(root, node);
  74.     ++heap_size;
  75.     return node;
  76.   }
  77.  
  78.   T top() {
  79.     if (root == NULL) throw "Cannot get min from empty heap";
  80.     return root->value;
  81.   }
  82.  
  83.   T deltop() {
  84.     if (root == NULL) throw "Cannot del min from empty heap";
  85.     LeftistHeapNode *tmp = root;
  86.     root = merge(root->left, root->right);
  87.     --heap_size;
  88.     tmp->left = tmp->right = NULL;
  89.     T value = tmp->value;
  90.     delete tmp;
  91.     return value;
  92.   }
  93.  
  94.   void merge(LeftistHeap &heap) {
  95.     root = merge(root, heap.root);
  96.     heap_size += heap.heap_size;
  97.     heap.root = NULL;
  98.     heap.heap_size = 0;
  99.   }
  100.  
  101.   size_t size() {
  102.     return heap_size;
  103.   }
  104. };
  105.  
  106. class FindUnion {
  107.   int *root, *rank;
  108.  
  109.  public:
  110.   FindUnion(int n) {
  111.     root = new int [n];
  112.     rank = new int [n];
  113.     for (int i = 0; i < n; ++i) root[i] = i;
  114.   }
  115.  
  116.   ~FindUnion() {
  117.     delete root;
  118.     delete rank;
  119.   }
  120.  
  121.   int find_set(int v) {
  122.     if (root[v] == v) return v;
  123.     root[v] = find_set(root[v]);
  124.     return root[v];
  125.   }
  126.  
  127.   void union_sets(int v, int u) {
  128.     v = find_set(v);
  129.     u = find_set(u);
  130.     if (rank[v] < rank[u]) {
  131.       root[v] = u;
  132.     } else if (rank[v] > rank[u]) {
  133.       root[u] = v;
  134.     } else {
  135.       root[v] = u;
  136.       ++rank[v];
  137.     }
  138.   }
  139. };
  140.  
  141. int main() {
  142.   int n, m;
  143.   scanf("%d %d", &n, &m);
  144.   vector<LeftistHeap<pair<int, pair<int, int> > > > edges(n);
  145.   FindUnion fu(n);
  146.   for (int i = 0; i < m; ++i) {
  147.     int a, b, c;
  148.     scanf("%d %d %d", &a, &b, &c);
  149.     --a, --b;
  150.     edges[a].insert(make_pair(c, make_pair(a, b)));
  151.     edges[b].insert(make_pair(c, make_pair(b, a)));
  152.   }
  153.  
  154.   vector<pair<int, int> > out;
  155.   for (int i = 1; i < n; ++i) {
  156.     int u, v = fu.find_set(i);
  157.     while ((u = fu.find_set(edges[v].top().second.second)) == v) {
  158.       edges[v].deltop();
  159.     }
  160.     out.push_back(edges[v].top().second);
  161.     fu.union_sets(u, v);
  162.     if (v != fu.find_set(v)) swap(u, v);
  163.     edges[v].merge(edges[u]);
  164.   }
  165.  
  166.   for (vector<pair<int, int> >::iterator it = out.begin(); it != out.end(); ++it) {
  167.     printf("%d %d\n", it->first + 1, it->second + 1);
  168.   }
  169.   return 0;
  170. }
  171.  
Success #stdin #stdout 0s 3040KB
comments (?)
stdin
copy 
11 14
2 11 1
5 7 2
3 11 3
3 7 4
7 9 5
9 10 6
8 9 7
2 7 8
7 10 9
1 2 10
2 6 11
3 10 12
5 10 13
3 4 14
stdout
copy 
2 11
3 11
4 3
5 7
6 2
7 3
8 9
9 7
10 9
2 1
https://ideone.com/qOF5EH
Boruvka
language:
C++ (gcc 8.3)
created:
11 years 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!