fork(1) download 
  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4. class dsu{
  5. public:
  6.     vector<int>par,sz;
  7.     int total_components;
  8.     void init (int n){
  9.        par.resize(n);
  10.        sz.resize(n);
  11.        //initially parent of all nodes are they themself
  12.        for(int i = 0;i < n; i++){
  13.         par[i] = i;
  14.        }
  15.        for(int i = 0;i < n; i++){
  16.         sz[i] = 1;
  17.        }
  18.        int total_components = n;
  19.     }
  20.     int get_superparent(int x){
  21.         //parent of all nodes are they themself
  22.         if(x == par[x]){
  23.             return x;
  24.         }
  25.         //path compression
  26.         return par[x] = get_superparent(par[x]);
  27.     }
  28.     //merging
  29.     void Union(int x, int y){
  30.         int superparent_x = get_superparent(x);
  31.         int superparent_y = get_superparent(y);
  32.         if(superparent_x != superparent_y){
  33.             par[superparent_x] = superparent_y;
  34.             sz[superparent_y]+=sz[superparent_x];
  35.             sz[superparent_x] = 0;
  36.             total_components--;
  37.         }
  38.     }
  39. };
  40. int main(){
  41.     dsu d;
  42.     int m_pairs, n_cities,ans;
  43.     cin>>n_cities>>m_pairs;
  44.     d.init(n_cities);
  45.     for(int i=0;i<m_pairs;i++){
  46.         int x,y;
  47.         cin>>x>>y;
  48.         d.Union(x,y);
  49.     }
  50.     for(int i=0;i<n_cities;i++){
  51.         int superparent_i = d.get_superparent(i);
  52.         ans+=(n_cities-d.sz[superparent_i]);
  53.     }
  54.     cout<<ans/2;
  55. return 0;}
  56.  
Success #stdin #stdout 0s 4196KB
comments (?)
stdin 
5 3
0 1
2 3 
0 4
stdout 
-157695130
https://ideone.com/AcomNv
language:
C++ (gcc 8.3)
created:
5 years 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!