Connect cities

#include <iostream>
#include <vector>

std::vector<std::vector<int>> connected_components;

void dfs(int current_node, std::vector<int> (&adj)[], bool (&visited)[]) {
    if (visited[current_node]) return;

    visited[current_node] = true;
    connected_components.back().push_back(current_node);
    for (auto node : adj[current_node]) {
        dfs(node, adj, visited);
    }
}

// find all connected components, then connect them with each other
int main() {
    
    int cities, roads;
    std::cin >> cities >> roads;

    std::vector<int> adj[cities];
    bool visited[cities] = {false};


    for (int i = 0; i < roads; i++) {
        int a, b;
        std::cin >> a >> b;

        a--, b--; // index of roads starts at 1
        adj[a].push_back(b);
        adj[b].push_back(a);

    }

    // std::cout << "----------------" << std::endl;

    // start dfs to find all connected components
    for (int i = 0; i < cities; i++) {
        
        if (!visited[i]) {
            connected_components.push_back(std::vector<int>());
            dfs(i, adj, visited);
        }
    }

    
    // print adjacency list
    // for (int i = 0; i < cities; i++) {
    //     for (int j = 0; j < adj[i].size(); j++) {
    //         std::cout << i+1 << ": " << adj[i][j]+1 << " ";
    //     }
    //     std::cout << std::endl;
    // }

    // print connected components
    // for (const auto& component : connected_components) {
    //     for (const auto& node : component) {
    //         std::cout << node << " ";
    //     }
    //     std::cout << std::endl;
    // }

    // std::cout << "----------------" << std::endl;

    // get road between connected components
    int num_connected_components = connected_components.size();
    if (num_connected_components > 1) {
        std::cout << num_connected_components - 1 << std::endl; // number of needed roads
        // get needed roads
        for (int component = 0; component < num_connected_components - 1; component++) {
            // int last_city = connected_components[component].size() - 1;
            std::cout << connected_components[component][0] + 1 << " " <<  connected_components[component + 1][0] + 1 << std::endl; // correct index again, cities start with index 1
        }
    } else {
        std::cout << "0" << std::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