Connect cities

#include <iostream>
#include <vector>
 
using namespace std;
 
void colorComponent(int v, int color, vector<int>& colors, vector<vector<int>>& g)
{
    colors[v] = color;
    for (auto u : g[v])
        if (colors[u] == 0)
            colorComponent(u, color, colors, g);
}
 
int main()
{
    ios::sync_with_stdio(false);
 
    int n = 0, m = 0;
    cin >> n >> m;
 
    vector<vector<int>> g(n);
    int u = 0, v = 0;
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    int curColor = 1;
    int lastV = -1;
    vector<int> colors(n);
    vector<pair<int, int>> toBuild;
    for (int i = 0; i < n; ++i)
    {
        if (colors[i] != 0)
            continue;
        colorComponent(i, curColor++, colors, g);
        if (lastV != -1)
            toBuild.emplace_back(lastV, i);
        lastV = i;
    }
 
    cout << toBuild.size() << "\n";
    for (const auto& [from, to] : toBuild)
        cout << from + 1 << " " << to + 1 << "\n";
 
    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