C - Connect Cities DSU.cpp

#include <bits/stdc++.h>
using namespace std;
  
struct DSU {
  vector<int> e;
  int SCC;
  DSU(int n) : e(n, -1), SCC(n) {}
  bool sameSet(int a, int b) { return find(a) == find(b); }
  int size(int x) { return -e[find(x)]; }
  int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
  bool join(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;
    if (e[a] > e[b]) swap(a, b);
    e[a] += e[b]; e[b] = a;
    SCC--;
    return true;
  }
};
  
void solve() {
  int n,m;
  cin >> n >> m;
  
  DSU dsu(n);
  
  for(int i=0;i<m;i++){
    int a,b;
    cin >> a >> b;
    --a,--b;
    dsu.join(a,b);
  }
  
  cout << dsu.SCC - 1 << "\n";
}
  
int main() {
  solve();
  
  return 0;
}