Connect cities

#include <iostream>
#include <vector>

using namespace std;

// Union-Find (Disjoint Set Union) structure to manage connected components
class UnionFind {
public:
    vector<int> parent, rank;

    UnionFind(int n) {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
        }
    }

    int find(int u) {
        if (u != parent[u]) {
            parent[u] = find(parent[u]);  // Path compression
        }
        return parent[u];
    }

    void unite(int u, int v) {
        int root_u = find(u);
        int root_v = find(v);
        if (root_u != root_v) {
            if (rank[root_u] > rank[root_v]) {
                parent[root_v] = root_u;
            } else if (rank[root_u] < rank[root_v]) {
                parent[root_u] = root_v;
            } else {
                parent[root_v] = root_u;
                rank[root_u]++;
            }
        }
    }
};

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

    UnionFind uf(n);

    // Read the roads and unite the connected cities
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        uf.unite(a, b);
    }

    // Find all the unique connected components
    vector<int> representatives;
    for (int i = 1; i <= n; ++i) {
        if (uf.find(i) == i) {
            representatives.push_back(i);
        }
    }

    // We need to connect (number of components - 1) roads
    int k = representatives.size() - 1;
    cout << k << endl;

    // Connect each pair of consecutive components
    for (size_t i = 1; i < representatives.size(); ++i) {
        cout << representatives[i - 1] << " " << representatives[i] << 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