Building Roads

Byteland has n cities and m roads between them. The goal is to construct new roads so that there is a route between any two cities.

Your task is to find out the minimum number of roads required, and also determine which roads should be built.

Example:

Input:  n = 4, m = 2, edges = {{1, 2}, {3, 4}}

Output:

1
1 3

Approach:

C++

#include <bits/stdc++.h>
using namespace std;
vector<int> arr[2000011];
int vis[2000011];
void dfs(int node)
{
    vis[node] = 1;
    for (int child : arr[node])
    {
        if (vis[child] == 0)
            dfs(child);
    }
}
int main()
{
    int n = 4, m = 2;
    vector<vector<int>> edges = {{1, 2}, {3, 4}};
    for (int i = 0; i < m; i++)
    {
        int a = edges[i][0], b = edges[i][1];

        arr[a].push_back(b);
        arr[b].push_back(a);
    }
    int cnt = 0;
    vector<int> path;
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
        {
            path.push_back(i);
            cnt++;
            dfs(i);
        }
    }
    if (cnt == 1)
        cout << 0 << "\n";
    else
    {
        cout << cnt - 1 << "\n";
        for (int i = 0; i < path.size() - 1; i++)
        {
            cout << path[i] << " " << path[i + 1] << "\n";
        }
    }
}