Connect cities

#include <vector>
struct UnionFind {
  std::vector<int> sets;
  int numSepSets;
  //sets[i] = x: if x<0, i is a root, and -x is the size else i is a child of parent x.
  UnionFind(int n) : sets(n, -1), numSepSets(n) {}
  bool sameRoot(int a, int b) { return find(a) == find(b); }
  int sizeOfSet(int x) { return -sets[find(x)]; }

  //Path compression
  int find(int x) 
  { 
    return sets[x] < 0 ? x : sets[x] = find(sets[x]); 
  }

  //Union by rank
  bool unionOf(int a, int b) 
  {
    a = find(a);
    b = find(b);
    if (a == b) return false;
    if (sets[a] > sets[b]) std::swap(a, b); // or if (-sets[a] < -sets[b]) std::swap(a, b);
    sets[a] += sets[b]; 
    sets[b] = a;
    --numSepSets;
    return true;
  }
};


#include <iostream>
int main(){
  int n, m;
  std::cin >> n >> m;
  UnionFind dsu(n);
  for (int road = 0; road<m; ++road){
    int city1, city2;
    std::cin >> city1 >> city2;
    dsu.unionOf(city1-1, city2-1);
  }

  std::cout << dsu.numSepSets - 1 << "\n";
  int root = 0;
  for (int city = 1; city<n; ++city){
    if (dsu.unionOf(root, city)){
      std::cout << root + 1 << " " << city + 1 << "\n";
    }
    if (dsu.numSepSets == 1) return 0;
  }
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED