Connect cities

#include <iostream>
#include <vector>

void dfs(int s, int l, int* visited, const std::vector<int> adj[], int n) {
    if (visited[s]) return;
    visited[s] = l;
    for (auto u : adj[s]) {
        dfs(u, l, visited, adj, n);
    }
}

int main()
{
    int n, m;
    std::cin >> n >> m;
    std::vector<int>* adj = new std::vector<int>[n];
    for (int i = 0; i < m; ++i) {
        int a, b;
        std::cin >> a >> b;
        adj[a-1].push_back(b-1);
        adj[b-1].push_back(a-1);
    }
    int* visited = new int[n]();
    
    int l = 1;
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i, l, visited, adj, n);
        }
        l++;
    }
    
    std::vector<int> r;
    for (int i = 0; i < n; i++) {
        int in = 0;
        for (long unsigned int j = 0; j < r.size(); ++j) {
            if (r[j] == visited[i]) {
                in = 1;
                break;
            }
        }
        if (!in) {
            r.push_back(visited[i]);
        }
    }
    
    std::cout << r.size() - 1 << std::endl;
    if (r.size() > 1){
        for (long unsigned int i = 0; i < r.size() - 1; ++i) {
            std::cout << r[i] << " " << r[i + 1] << std::endl;
        }
    }
}

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

Test 12

Verdict: ACCEPTED