Connect cities

#include <iostream>
#include <vector>

using namespace std;

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

void find_minimum_roads(int n, int m, const vector<pair<int, int>>& roads) {
    vector<vector<int>> adj(n + 1);
    for (const auto& road : roads) {
        adj[road.first].push_back(road.second);
        adj[road.second].push_back(road.first);
    }

    vector<bool> visited(n + 1, false);
    vector<int> components;

    for (int city = 1; city <= n; ++city) {
        if (!visited[city]) {
            components.push_back(city);
            dfs(city, visited, adj);
        }
    }

    if (components.size() == 1) {
        cout << 0 << endl;
        return;
    }

    cout << components.size() - 1 << endl;
    for (size_t i = 1; i < components.size(); ++i) {
        cout << components[i - 1] << " " << components[i] << endl;
    }
}

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

    vector<pair<int, int>> roads(m);
    for (int i = 0; i < m; ++i) {
        cin >> roads[i].first >> roads[i].second;
    }

    find_minimum_roads(n, m, roads);

    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