CSES Problem Set Building Roads Solution

Problem Link:  https://cses.fi/problemset/task/1666  

Solution in C++: 

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include<bits/stdc++.h>

using namespace std;

#define mx 100009

int node, edge, i,j,u,v,x,y;

vector<int>g[mx];

bool visited[mx]= {0};

vector<int>vp;

void dfs(int u)

{

    visited[u]=1;

    for (auto child : g[u])

    {

        if (visited[child] == 0)

        {

            dfs(child);

        }

    }

}

int main()

{

    cin>>node>>edge;

    for(i=1; i<=edge; i++)

    {

        cin>>u>>v;

        g[u].push_back(v);

        g[v].push_back(u);

    }

    for(i=1; i<=node; i++)

    {

        if(visited[i]==0)

        {

            vp.push_back(i);

            dfs(i);

        }

    }

    cout<<vp.size()-1<<endl;

    for(i=0; i<vp.size()-1; i++)

    {

        cout<<vp[i]<<" "<<vp[i+1]<<endl;

    }

}