Language: C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct UnionFind {
  vector<long> islandLinks;
  
  UnionFind(int n) : islandLinks(n, -1) {}
  
  int root(int x) {
    if(islandLinks[x] < 0) return x;
    return root(islandLinks[x]);
  }
  
  bool isSame(int x, int y) {
    if(root(x) == root(y)) return true;
    return false;
  }
  
  bool merage(int x, int y) {
    if(root(x) == root(y)) return false;
    
    if(root(x) > root(y)) swap(x, y);
    islandLinks[root(x)] += islandLinks[root(y)];
    islandLinks[root(y)] = x;
    return true;
  }
  
  long size(int x) {
    return -islandLinks[root(x)];
  }
};

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(M), B(M);
  
  for(int i = 0; i < M; i++){
    cin >> A[i] >> B[i];
  }
  
  long count = N*(N-1) * 0.5; 
  vector<long> weights;
  
  UnionFind uf(N);
  for(int i = 0; i < M; i++) {
    weights.push_back(count);
    
    if(uf.isSame(A[N-1-i], B[N-1-i])) continue;
    
    long sa = uf.size(A[N-1-i]), sb = uf.size(B[N-1-i]);
    count -= sa*sb;
    
    uf.merage(A[N-1-i],B[N-1-i]);
  }
  
  iterator<long> iter = weights.rbegin();
  while(iter != weights.rend()) {
    cout << *iter << endl;
    iter++;
  }

Compiler output:
a.cc: In function 'int main()':
a.cc:60:3: warning: 'template<class _Category, class _Tp, class _Distance, class _Pointer, class _Reference> struct std::iterator' is deprecated [-Wdeprecated-declarations]
   60 |   iterator<long> iter = weights.rbegin();
      |   ^~~~~~~~
In file included from /usr/include/c++/14/bits/stl_iterator_base_funcs.h:66,
                 from /usr/include/c++/14/string:47,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_iterator_base_types.h:127:34: note: declared here
  127 |     struct _GLIBCXX17_DEPRECATED iterator
      |                                  ^~~~~~~~
a.cc:60:16: error: wrong number of template arguments (1, should be at least 2)
   60 |   iterator<long> iter = weights.rbegin();
      |                ^
/usr/include/c++/14/bits/stl_iterator_base_types.h:127:34: note: provided for 'template<class _Category, class _Tp, class _Distance, class _Pointer, class _Reference> struct std::iterator'
  127 |     struct _GLIBCXX17_DEPRECATED iterator
      |                                  ^~~~~~~~
a.cc:60:39: error: cannot convert 'std::vector<long int>::reverse_iterator' {aka 'std::reverse_iterator<__gnu_cxx::__normal_iterator<long int*, std::vector<long int> > >'} to 'int' in initialization
   60 |   iterator<long> iter = weights.rbegin();
      |                         ~~~~~~~~~~~~~~^~
      |                                       |
      |                                       std::vector<long int>::reverse_iterator {aka std::reverse_iterator<__gnu_cxx::__normal_iterator<long int*, std::vector<long int> > >}
a.cc:61:14: error: no match for 'operator!=' (operand types are 'int' and 'std::vector<long int>::reverse_iterator' {aka 'std::reverse_iterator<__gnu_cxx::__normal_iterator<long int*, std::vector<long int> > >'})
   61 |   while(iter != weights.rend()) {
      |         ~~~~ ^~ ~~~~~~~~~~~~~~
      |         |                   |
      |         int                 std::vector<long int>::reverse_iterator {aka std::reverse_iterator<__gnu_cxx::__normal_iterator<long int*, std::vector<long int> > >}
In file included from /usr/include/c++/14/iosfwd:42,
                 from /usr/include/c++/14/ios:40:
/usr/include/c++/14/bits/postypes.h:197:5: note: candidate: 'template<class _StateT> bool std::operator!=(const fpos<_StateT>&, const fpos<_StateT>&)'
  197 |     operator!=(const fpos<_StateT>& __lhs, const fpos<_StateT>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/14/bits/postypes.h:197:5: note:   template argument deduction/substitution failed:
a.cc:61:30: note:   mismatched types 'const std::fpos<_StateT>' and 'int'
   61 |   while(iter != weights.rend()) {
      |                              ^
In file included from /usr/include/c++/14/string:43:
/usr/include/c++/14/bits/allocator.h:243:5: note: candidate: 'template<class _T1, class _T2> bool std::operator!=(const allocator<_CharT>&, const allocator<_T2>&)'
  243 |     operator!=(const allocator<_T1>&, const allocator<_T2>&)
      |     ^~~~~~~~
/usr/include/c++/14/bits/allocator.h:243:5: note:   template argument deduction/substitution failed:
a.cc:61:30: note:   mismatched types 'const std::allocator<_CharT>' and 'int'
   61 |   while(iter != weights.rend()) {
      |                              ^
In file included from /usr/include/c++/14/string:48:
/usr/include/c++/14/bits/stl_iterator.h:455:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator!=(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  455 |     operator!=(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:455:5: note:   template argument deduction/substitution failed:
a.cc:61:30: note:   mismatched types 'const std::reverse_iterator<_Iterator>' and 'int'
   61 |   while(iter != weights.rend()) {
      |                              ^
/usr/include/c++/14/bits/stl_iterator.h:500:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator!=(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  500 |     operator!=(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:500:5: note:   template argument deduction/substitution failed:
a.cc:61:30: note:   mismatched types 'const std::reverse_iterator<_Iterator>' and 'int'
   61 |   while(iter != weights.rend()) {
      |                              ^
/usr/include/c++/14/bits/stl_iterator.h:1686:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator!=(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1686 |     operator!=(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1686:5: note:   template argument deduction/substitution failed:
a.cc:61:30: note:   mismatched types 'const std::move_iterator<_IteratorL>' and 'int'
   61 |   while(iter != weights.rend()) {
      |                              ^
/usr/include/c++/14/bits/stl_iterator.h:1753:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator!=(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)'
 1753 |     operator!=(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1753:5: note:   template argument deduction/substitution failed:
a.cc:61:30: note:   mismatched types 'const std::move_iterator<_IteratorL>' and 'int'
   61 |   while(iter != weights.rend()) {
      |                              ^
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/string:51:
/usr/include/c++/14/bits/stl_pair.h:1052:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator!=(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1052 |     operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1052:5: note:   template argument deduction/substitution failed:
a.cc:61:30: note:   mismatched types 'const std::pair<_T1, _T2>' and 'int'
   61 |   while(iter != weights.rend()) {
      |                              ^
In file included from /usr/include/c++/14/bits/basic_string.h:47,
                 from /usr/include/c++/14/string:54:
/usr/include/c++/14/string_view:651:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator!=(basic_string_view<_CharT, _Traits>, basic_string_view<_CharT, _Traits>)'
  651 |     operator!=(basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/14/string_view:651:5: note:   template argument deduction/substitution failed:
a.cc:61:30: note:   mismatched types 'std::basic_string_view<_CharT, _Traits>' and 'int'
   61 |   while(iter != weights.rend()) {
      |                              ^
/usr/include/c++/14/string_view:658:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator!=(basic_string_view<_CharT, _Traits>, __type_identity_t<basic_string_view<_CharT, _Traits> >)'
  658 |     operator!=(basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/14/string_view:658:5: note:   template argument deduction/substitution failed:
a.cc:61:30: note:   mismatched types 'std::basic_string_view<_CharT, _Traits>' and 'int'
   61 |   while(iter != weights.rend()) {
      |                              ^
/usr/include/c++/14/string_view:666:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator!=(__type_identity_t<basic_string_view<_CharT, _Traits> >, basic_string_view<_CharT, _Traits>)'
  666 |     operator!=(__type_identity_t<basic_string_view<_CharT, _Traits>> __x,
      |     ^~~~~~~~
/usr/include/c++/14/string_view:666:5: note:   template argument deduction/substitution failed:
a.cc:61:30: note:   'std::reverse_iterator<__gnu_cxx::__normal_iterator<long int*, std::vector<long int> > >' is not derived from 'std::basic_string_view<_CharT, _Traits>'
   61 |   while(iter != weights.rend()) {
      |                              ^
/usr/include/c++/14/bits/basic_string.h:3833:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator!=(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 3833 |     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:3833:5: note:   template argument deduction/substitution failed:
a.cc:61:30: note:   mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
   61 |   while(iter != weights.rend()) {
      |                              ^
/usr/include/c++/14/bits/basic_string.h:3847:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator!=(const _CharT*, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 3847 |     operator!=(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:3847:5: note:   template argument deduction/substitution failed:
a.cc:61:30: note:   mismatched types 'const _CharT*' and 'int'
   61 |   while(iter != weights.rend()) {
      |                              ^
/usr/include/c++/14/bits/basic_string.h:3860:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator!=(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)'
 3860 |     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/basic_string.h:3860:5: note:   template argument deduction/substitution failed:
a.cc:61:30: note:   mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
   61 |   while(iter != weights.rend()) {
      |                              ^
In file included from /usr/include/c++/14/bits/memory_resource.h