kananasgarli90

Building Roads

Oct 28th, 2020
887
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<int>adj[100001];
  4. vector<int>v;
  5. int a, b, n, m, u, color[100001];
  6.  
  7. void dfs(int s){
  8.     color[s] = 1;
  9.     for(int i = 0; i < adj[s].size(); i++){
  10.         u = adj[s][i];
  11.         if(color[u] == 0){
  12.             dfs(u);
  13.         }
  14.     }
  15. }
  16. int main()
  17. {
  18.     cin>>n>>m;
  19.     while(m--){
  20.         cin>>a>>b;
  21.         adj[a].push_back(b);
  22.         adj[b].push_back(a);
  23.     }
  24.     for(int i = 1; i <= n; i++){
  25.         if(color[i] == 0){
  26.             v.push_back(i);
  27.             dfs(i);
  28.         }
  29.     }
  30.     cout<<v.size()-1<<endl;
  31.     for(int i = 0; i < v.size()-1; i++){
  32.         cout<<v[i]<<" "<<v[i+1]<<endl;
  33.     }
  34. }
  35.  
RAW Paste Data