fork download
copy 
  1. // Insteading breaking/damaging edges thinking of answering in reverse order helps
  2. // in such problems , here merging in reverse order means making available edges at a particulartime
  3. // If we dont think in reverse way this problem may take more time complexity to solve
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define int long long
  7. int par[100005];
  8. int group_size[100005];
  9. int answer;
  10.  
  11. // Disjoint set data structure
  12. int find(int i)
  13. {
  14.     if(par[i] == i)return i;
  15.     return par[i] = find(par[i]);
  16. }
  17. void merge(int a,int b)
  18. {
  19.     a = find(a);
  20.     b = find(b);
  21.     if(a == b)
  22.         return;
  23.     // Retriving previously considered inconvinience pairs
  24.     answer += (group_size[a]*(group_size[a]-1)/2);
  25.     answer += (group_size[b]*(group_size[b]-1)/2);
  26.  
  27.     par[b] = a;
  28.     group_size[a]+=group_size[b];
  29.  
  30.     // adding new inconvinience pairs
  31.     answer -= (group_size[a]*(group_size[a]-1)/2);
  32. }
  33.  
  34. signed main()
  35. {    
  36.  
  37.     int n,m;
  38.     cin >> n >> m;
  39.     for(int i=1;i<=n;i++)
  40.     {
  41.         par[i] = i;
  42.         group_size[i] = 1;
  43.     }
  44.     vector<pair<int,int>> edges;
  45.     for(int i=0;i<m;i++)
  46.     {
  47.         int u,v;cin >> u >> v;
  48.         edges.push_back({u,v});
  49.     }
  50.  
  51.     // Answering queries in reverse order
  52.     // before the first state there will be no merged points so answer will be n*(n-1)/3 [all are invonvient]
  53.     answer = n*(n-1)/2;
  54.  
  55.     reverse(edges.begin(),edges.end());
  56.  
  57.     vector<int> query_answers;
  58.  
  59.     for(auto e:edges)
  60.     {
  61.         query_answers.push_back(answer);
  62.  
  63.         int u = e.first;
  64.         int v = e.second;
  65.  
  66.         // already part of same group
  67.         if(find(u) == find(v)) continue;
  68.  
  69.         merge(u,v);
  70.     }
  71.  
  72.  
  73.     // reversing answers
  74.     reverse(query_answers.begin(),query_answers.end());
  75.  
  76.     for(int ans:query_answers)
  77.     {
  78.         cout << ans << '\n';
  79.     }
  80.  
  81. }
  82.  
Success #stdin #stdout 0s 5584KB
comments (?)
stdin
copy 
4 5
1 2
3 4 
1 3 
2 3
1 4
stdout
copy 
0
0
4
5
6
https://ideone.com/R9mAeV
language:
C++14 (gcc 8.3)
created:
2 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!