[NEW] Add solution for Building Roads

[vingoel26]

🎯 Problem Information

• Problem Name: Building Roads
• CSES Link: https://cses.fi/problemset/task/1666
• Category: Graphs
• Estimated Difficulty: Medium

📋 Problem Description

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.

💡 Proposed Approach

Describe the algorithm/approach you plan to use:

• The code implements DFS traversal to find all connected components in an undirected graph.

• Once all components are identified, it outputs the minimum number of edges required to make the graph connected.

• Specifically:

  • It performs DFS for every unvisited node.
  • Stores one representative vertex per component.
  • Then connects consecutive component representatives to form a single connected graph.

• Time Complexity: O(N + M)

• Space Complexity: O(N + M)

---

📝 Implementation Notes

Any special considerations or optimizations needed:

• Requires fast I/O
• Needs modular arithmetic
• Large input constraints (N ≤ 1e5)
• Edge cases to consider:
  • Disconnected graphs
  • Single node (n = 1)
  • Already connected graph

---

🏷️ Labels

Please add appropriate labels:

• hacktoberfest
• good first issue
• help wanted

---

👤 Assignee

• I would like to work on this issue
• I'm available for guidance/review

---

Code Implementation

#include <bits/stdc++.h>
#define int long long
#define inp(n) \
    int n;     \
    cin >> n
#define vin(a)                  \
    for (int i = 0; i < n; ++i) \
    {                           \
        cin >> a[i];            \
    }
#define vout(a)                 \
    for (int i = 0; i < n; ++i) \
    {                           \
        cout << a[i] << ' ';    \
    }
#define pb push_back
#define ff first
#define ss second
#define viv vector<vector<int>>
#define nah cout << "NO\n";
#define yah cout << "YES\n";
#define be begin()
#define en end()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define vi vector<int>
#define vpi vector<pair<int, int>>
#define up upper_bound
#define low lower_bound
#define mod 1000000007
using namespace std;

/*
========================================
Author:         Vinayak Goel
Institution:    IIITL
May the WA avoid you
========================================
*/

const int N = 1e5 + 9;
vector<int> g[N];
bool vis[N];

void dfs(int u)
{
    vis[u] = true;
    for (auto v : g[u])
    {
        if (!vis[v])
            dfs(v);
    }
}

void solve()
{
    int n, m;
    cin >> n >> m;
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> c;
    for (int u = 1; u <= n; u++)
    {
        if (!vis[u])
        {
            c.push_back(u);
            dfs(u);
        }
    }

    cout << c.size() - 1 << endl;
    for (int i = 0; i + 1 < c.size(); i++)
    {
        cout << c[i] << ' ' << c[i + 1] << endl;
    }
}

int32_t main()
{
    fast
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

[vingoel26]

@ks-iitjmu please assign this to me