Connect cities

#include <vector>
#include <iostream>

using namespace std;

void dfs(int n, vector<bool> &visited, const vector<vector<int>> adj);

int main()
{

    int n;
    int m;
    cin >> n;
    cin >> m;

    vector<vector<int>> adja(n);
    int result = 0;
    vector<pair<int, int>> new_roads;

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

    // cout << "Adjacencies done";
    // for (int i = 0; i < n; i++)
    // {
    //     cout << i;
    //     for (int neighbors : adja[i])
    //     {
    //         cout << neighbors << " ";
    //     }
    //     cout << "\n";
    // }

    vector<bool> visited(n);

    dfs(0, visited, adja);

    while (true)
    {
        int node = -1;
        for (int i = 0; i < n; i++)
        {
            if (visited[i] == false)
            {
                node = i;
                break;
            }
        }
        if (node == -1)
        {
            break;
        }
        result += 1;
        new_roads.push_back({0, node});
        dfs(node, visited, adja);
    }

    cout << result << "\n";
    for (pair<int, int> road : new_roads)
    {
        cout << road.first + 1 << " " << road.second + 1 << "\n";
    }
}

void dfs(int n, vector<bool> &visited, const vector<vector<int>> adj)
{
    if (visited[n])
    {
        return;
    }
    visited[n] = true;
    for (int neighbor : adj[n])
    {
        dfs(neighbor, visited, adj);
    }
}

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: TIME LIMIT EXCEEDED

Test 12

Verdict: ACCEPTED