Connect cities

#include <algorithm>
#include <any>
#include <compare>
#include <iostream>
#include <numeric>
#include <set>
#include <utility>
#include <vector>

using namespace std;

template <typename T>
std::ostream &operator<<(std::ostream &os, const vector<T> &obj) {
    bool first = true;
    // cout << "vec" << endl;
    for (const auto &o : obj) {
        if (first) {
            cout << o;
            first = false;
        } else {
            cout << ' ' << o;
        }
    }
    cout << endl;
    return os;
}

std::ostream &operator<<(std::ostream &os, const vector<pair<int, int>> &obj) {
    for (const auto &o : obj) {
        cout << o.first << ' ' << o.second << endl;
    }
    cout << endl;
    return os;
}

vector<vector<int>> old_roads;

// vector<bool> visited;

// vector<int> grandparent;
// set<set<int>> all_roads;

void province_dfs(int c, set<int> &out) {
    if (out.contains(c))
        return;
    out.insert(c);
    for (const auto &nb : old_roads[c - 1]) {
        province_dfs(nb, out);
    }
}

// bool connected_dfs(int a, int b) {
//     if (all_roads.contains({a, b})) {
//         visited[a] = true;
//         return true;
//     }
//     if (visited[a])
//         return false;
//     visited[a] = true;
//
//     bool conn = false;
//     for (const auto &c : old_roads[a]) {
//         conn |= connected_dfs(c, b);
//     }
//     return conn;
// }
/**
 *
 */
int main(int argc, char **argv) {
    int n_cities, n_roads;
    cin >> n_cities >> n_roads;

    vector<int> cities(n_cities);
    iota(cities.begin(), cities.end(), 1);
    for (int i = 0; i < n_cities; ++i)
        old_roads.push_back({});
    for (int i = 0; i < n_roads; ++i) {
        int a, b;
        cin >> a >> b;
        old_roads[a - 1].push_back(b);
        old_roads[b - 1].push_back(a);
    }

    // cout << "here" << endl;

    set<int> connected;
    set<int> province_tmp;
    vector<pair<int, int>> new_roads;
    for (int city : cities) {
        if (!connected.contains(city)) {
            // Find province
            province_dfs(city, province_tmp);
            connected.insert(province_tmp.begin(), province_tmp.end());
            province_tmp.clear();
            if (city != 1)
                new_roads.push_back({1, city});
        }
    }

    cout << new_roads.size() << endl;
    cout << new_roads;
}

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