Connect cities

#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << ' ' << x << endl;

const int INF = 1e9+7;

void dfs(int node, vector<int> adj[], bool visited[]) {
    visited[node] = true;
    // Process the current node
    
    for (int neighbor : adj[node]) {
        if (visited[neighbor] == false) {
            dfs(neighbor, adj, visited);
        }
    }
}

int main() {
    
    int n,m;
    cin >> n >> m;

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

    bool visited[n];
    for (int i = 0; i < n; ++i) visited[i] = false;

    vector<int> representatives;
    for (int i = 0; i < n; i++)
    {
        if (visited[i] == false)
        {
            representatives.push_back(i);
            dfs(i, neighs, visited);
        }
    }


    int nb_roads = representatives.size() - 1;
    cout << nb_roads << endl;

    if (nb_roads == 0) return 0;

    for (int i = 0; i < nb_roads; i++)
    {
        cout << representatives[i] +1 << ' ' << representatives[i+1] +1 << endl;
    }
    

    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