fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. void dfs(vector<vector<int>>&graphs,vector<bool>&vis,int i){
  6.  
  7. 	vis[i]=true;
  8.  
  9. 	for(auto j:graphs[i]){
  10. 		if(!vis[j]){
  11. 			dfs(graphs,vis,j);
  12. 		}
  13. 	}
  14. }
  15.  
  16. int main() {
  17. 	int n,m;
  18. 	cin>>n>>m;
  19.  
  20. 	vector<vector<int>>graphs(n+1);
  21. 	for(int i=0;i<m;i++){
  22. 		int a,b;
  23. 		cin>>a>>b;
  24. 		graphs[a].push_back(b);
  25. 		graphs[b].push_back(a);
  26. 	}
  27.  
  28. 	vector<bool>vis(n+1,false);
  29. 	vector<int>res;
  30. 	int ans=0;
  31.  
  32. 	for(int i=1;i<=n;i++){
  33. 		if(!vis[i]){
  34. 			ans++;
  35. 			res.push_back(i);
  36. 			dfs(graphs,vis,i);
  37. 		}
  38. 	}
  39.  
  40. 	if(ans==1){
  41. 		cout<<0<<endl;
  42. 	}
  43.  
  44. 	else{
  45. 	cout<<ans-1<<endl;
  46. 	for(int i=0;i<res.size()-1;i++){
  47. 		cout<<res[i]<<" "<<res[i+1]<<endl;
  48. 	}
  49. 	}
  50.  
  51. 	return 0;
  52. }
Success #stdin #stdout 0.01s 5520KB
comments (?)
stdin
copy 
4 2
1 2
3 4
stdout
copy 
1
1 3
https://ideone.com/D4kAeo
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!