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.
Input
The first input line has two integers n and m: the number of cities and roads.
The cities are numbered 1,2,…,n.
After that, there are m lines describing the roads.
Each line has two integers a and b: there is a road between those cities.
A road always connects two different cities, and there is at most one road between
any two cities.
Output
First print an integer k: the number of required roads.
Then, print k lines that describe the new roads. You can print any valid solution.
Constraints
1≤n≤105
1≤m≤2⋅105
1≤a,b≤n
Example
Input:
4 2
1 2
3 4
Output:
1
Using Normal DFS
/*<https://cses.fi/problemset/task/1666*/>
#include<bits/stdc++.h>
using namespace std;
vector<bool> visited;
vector<vector<int>> adj;
vector<int> temp;//contains the vertices of one scc
void dfs(int u)
{
if(visited[u])
return;
visited[u] = true;
for(int v:adj[u])
{
if(!visited[v])
dfs(v);
}
temp.push_back(u);
}
int main(void)
{
int m,n;
cin>>m>>n;
adj.resize(m+1);
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
adj[a].push_back(b);//creating adj list
adj[b].push_back(a);
}
visited.resize(m+1,false);
vector<vector<int>> cc;
int scc = 0;
//performing dfs
for(int i=1;i<=m;i++)
{
if(!visited[i])
{
dfs(i);
cc.push_back(temp);
temp.clear();
scc++;//incrementing the no. of strongly connected components at the end of each dfs call
}
}
cout<<scc-1<<endl;//no. of roads required
vector<vector<int>> res;
for(int i=0;i<cc.size()-1;i++)
{
cout<<cc[i][0]<<" "<<cc[i+1][0]<<endl;//road from one scc to another
}
}