Connect cities

input/code.cpp: In function 'int main()':
input/code.cpp:39:13: warning: variable 'm' set but not used [-Wunused-but-set-variable]
   39 |   for (auto m : roads) {
      |             ^
input/code.cpp:72:15: warning: unused variable 'c' [-Wunused-variable]
   72 |     for (auto c : island) {
      |               ^

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef set<int> si;
typedef set<set<int>> ssi;
typedef vector<pair<int, int>> vpi;
#define F first
#define S second
#define PB push_back
#define MP make_pair

#if DO_DBG
#define DBG(x) cerr << x << "\n";
#define DBG2(x) cerr << x;
#else
#define DBG(x)
#define DBG2(x)
#endif

#define loop(n) for (int i = 0; i < n; i++)

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  DBG("INIT")
  int n, m;
  cin >> n >> m;
  vpi roads;
  loop(m) {
    int src, dst;
    cin >> src >> dst;
    roads.push_back(MP(src, dst));
  }
  DBG("n: " << n)
  DBG("m: " << m)
  for (auto m : roads) {
    DBG(m.F << " -> " << m.S)
  }
  ssi islands;
  loop(n) { islands.insert(si{i + 1}); }

  for (auto m : roads) {
    auto i1res = find_if(islands.begin(), islands.end(),
                         [&m](const si &i) { return i.contains(m.F); });
    auto i2res = find_if(islands.begin(), islands.end(),
                         [&m](const si &i) { return i.contains(m.S); });
    if (i1res == islands.end() && i2res != islands.end()) {
      si newi2 = *i2res;
      newi2.insert(m.F);
      islands.erase(i2res);
      islands.insert(newi2);
    } else if (i2res == islands.end() && i1res != islands.end()) {
      si newi1 = *i1res;
      newi1.insert(m.F);
      islands.erase(i1res);
      islands.insert(newi1);
    } else if (i2res == islands.end() && i1res == islands.end()) {
      islands.insert(si{m.F, m.S});
    } else if (i2res != i1res) {
      si newIsland = si{*i2res};
      newIsland.insert(i1res->begin(), i1res->end());
      islands.erase(i1res);
      islands.erase(i2res);
      islands.insert(newIsland);
    }
  }
  for (auto island : islands) {
    DBG("ISLAND:")
    for (auto c : island) {
      DBG2(c << ", ")
    }
    DBG("")
  }
  cout << islands.size() - 1 << "\n";
  auto hub = *islands.begin();
  islands.erase(islands.begin());
  auto hubi = *hub.begin();
  for (auto island : islands) {
    auto gw = *island.begin();
    cout << hubi << " " << gw << "\n";
  }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED