C - Connect Cities.cpp

#include <bits/stdc++.h>
using namespace std;

vector<bool> vis;
vector<vector<int>> g;

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  for(int v : g[u]) {
    dfs(v);
  }
}

void solve() {
  int n,m;
  cin >> n >> m;

  g.assign(n, {});

  for(int i=0;i<m;i++){
    int a,b;
    cin >> a >> b;
    --a,--b;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  vis.assign(n, false);
  int numComp = 0;
  for(int i=0;i<n;i++){
    if (!vis[i]) {
      dfs(i);
      numComp++;
    }
  }

  cout << numComp - 1 << "\n";
}

int main() {
  solve();

  return 0;
}