fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include<algorithm>
  5. #include<string>
  6.  
  7. #define int long long
  8.  
  9. using namespace std;
  10.  
  11. class DSU {
  12. private:
  13.     vector<int>parent, rank, sz;
  14.     int comp = 0, maxi = 0;
  15.     stack < pair<int, pair<int, int>>>history;
  16.     stack<int>checkpoint;
  17. public:
  18.     DSU(int n) {
  19.         parent.resize(n + 1);
  20.         rank.resize(n + 1);
  21.         sz.assign(n + 1, 1);
  22.         comp = n;
  23.         maxi = 1;
  24.         for (int i = 0; i <= n; i++) parent[i] = i;
  25.     }
  26.  
  27.     int find_root(int node) {
  28.         if (node == parent[node]) return node;
  29.         return find_root(parent[node]);
  30.     }
  31.  
  32.     int union_by_rank(int u, int v) {
  33.         int root_u = find_root(u), root_v = find_root(v);
  34.         if (root_u == root_v) return comp;
  35.         comp--;
  36.         if (rank[root_u] > rank[root_v]) {
  37.             history.push({ 0, {root_v, parent[root_v]} });
  38.             parent[root_v] = root_u;
  39.         }
  40.         else {
  41.             history.push({ 0, {root_u, parent[root_u]} });
  42.             parent[root_u] = root_v;
  43.             if (rank[root_u] == rank[root_v]) {
  44.                 history.push({ 1, {root_v, rank[root_v]} });
  45.                 rank[root_v]++;
  46.             }
  47.         }
  48.         return comp;
  49.     }
  50.  
  51.     int union_by_size(int u, int v) {
  52.         int root_u = find_root(u), root_v = find_root(v);
  53.         if (root_u == root_v) return comp;
  54.         comp--;
  55.         if (sz[root_u] < sz[root_v]) {
  56.             history.push({ 0, {root_u, parent[root_u]} });
  57.             history.push({ 2, {root_v, sz[root_v]} });
  58.             parent[root_u] = root_v;
  59.             sz[root_v] += sz[root_u];
  60.         }
  61.         else {
  62.             history.push({ 0, {root_v, parent[root_v]} });
  63.             history.push({ 2, {root_u, sz[root_u]} });
  64.             parent[root_v] = root_u;
  65.             sz[root_u] += sz[root_v];
  66.         }
  67.         maxi = max({ maxi, sz[root_v], sz[root_u] });
  68.         return comp;
  69.     }
  70.  
  71.     void presist() {
  72.         checkpoint.push(history.size());
  73.     }
  74.  
  75.     int rollback() {
  76.         if (checkpoint.empty()) return comp;
  77.         int check = checkpoint.top();
  78.         checkpoint.pop();
  79.         while (history.size() > check) {
  80.             int type = history.top().first, node = history.top().second.first, last_val = history.top().second.second;
  81.             history.pop();
  82.             if (type == 0) { // parent
  83.                 if (parent[node] != node) {
  84.                     comp++;
  85.                 }
  86.                 parent[node] = last_val;
  87.  
  88.             }
  89.             else if (type == 1) { // rank
  90.                 rank[node] = last_val;
  91.             }
  92.             else{ // size
  93.                 sz[node] = last_val;
  94.             }
  95.         }
  96.         return comp;
  97.     }
  98.  
  99.     int unite(int u, int v) {
  100.         return union_by_size(u, v);
  101.     }
  102.  
  103.     bool are_connected(int u, int v) {
  104.         return find_root(u) == find_root(v);
  105.     }
  106.  
  107.     int mx_comp() {
  108.         int k = maxi;
  109.         return maxi;
  110.     }
  111.  
  112.     int get_size(int u) {
  113.         return sz[find_root(u)];
  114.     }
  115.  
  116. };
  117.  
  118. pair<int, vector<pair<int, int>>> MST(vector < pair<int, pair<int, int>>> edges, int n) {
  119.     sort(edges.begin(), edges.end());
  120.     vector<pair<int, int>>mst_edges;
  121.     int total = 0;
  122.     DSU d(n);
  123.     for (auto& it : edges) {
  124.         int cost = it.first, u = it.second.first, v = it.second.second;
  125.         if (!d.are_connected(u, v)) {
  126.             d.unite(u, v);
  127.             mst_edges.push_back({ u, v });
  128.             total += cost;
  129.         }
  130.     }
  131.     return { total, mst_edges };
  132. }
  133.  
  134. signed main() {
  135.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  136.  
  137.     return 0;
  138. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Sm0eHq
language:
C++14 (gcc 8.3)
created:
346 days ago
visibility:
secret

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!