fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define f first
  7. #define s second
  8. #define mp make_pair
  9. #define lb lower_bound
  10. #define ub upper_bound
  11. #define trav(a, x) for (auto& a: x)
  12. #define ins insert
  13. #define pq priority_queue
  14. #define all(v) v.begin(), v.end()
  15. #define sz(x) (int)x.size()
  16. #define endl "\n"
  17.  
  18. typedef long long ll;
  19. typedef vector<int> vi;
  20. typedef vector<ll> vll;
  21. typedef pair<int, int> pii; 
  22.  
  23. const int dx[4]= {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
  24.  
  25. void setIO(string name){
  26. 	ios_base::sync_with_stdio(0); cin.tie(0);
  27. 	freopen((name + ".in").c_str(), "r", stdin);
  28. 	freopen((name + ".out").c_str(), "w", stdout);
  29. }
  30.  
  31. int n, m;
  32. vector<int> adj[100005];
  33. bool visited[100005];
  34. int last = -1;
  35.  
  36. void dfs(int x){
  37.     last = x;
  38.     visited[x] = true;
  39.     trav(a, adj[x]){
  40.         if (!visited[a])
  41.             dfs(a);
  42.     }
  43. }
  44.  
  45. int main() {
  46.     // setIO("name");
  47.     cin >> n >> m;
  48.     for (int i = 0; i < m; i++){
  49.         int a, b; cin >> a >> b;
  50.         adj[a].pb(b);
  51.         adj[b].pb(a);
  52.     }
  53.  
  54.     vector<pii> answers;
  55.     int cnt = 0;
  56.     for (int i = 1; i <= n; i++){
  57.         if (!visited[i]){
  58.             if (i != 1){
  59.                 answers.pb(mp(last, i));
  60.                 cnt++;
  61.             }
  62.             dfs(i);
  63.         }
  64.     }
  65.  
  66.     cout << cnt << endl;
  67.     for (int i = 0; i < sz(answers); i++)
  68.         cout << answers[i].f << " " << answers[i].s << endl;
  69.  
  70.     return 0;
  71. }
Success #stdin #stdout 0s 5888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/q5NCal
Building Roads
language:
C++14 (clang 8.0)
created:
3 years 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!