fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct Node {
  4.     int rank;
  5.     int parent;
  6. };
  7. const int N = 200000;
  8. int n, m;
  9. Node dsu[N];
  10. vector<vector<int> > graph(N);
  11. bool visited[N];
  12. int minval, maxval;
  13. vector<pair<int,int> > maxmin;
  14.  
  15. void dfs(int node) {
  16.     visited[node] = true;
  17.     minval = min(minval, node);
  18.     maxval = max(maxval, node);
  19.     for(int &neighbour : graph[node])
  20.         if(!visited[neighbour])
  21.             dfs(neighbour);
  22.     return;
  23. }
  24. int root(int node) {
  25.     if(dsu[node].parent == node) return node;
  26.     dsu[node].parent = root(dsu[node].parent);
  27.     return dsu[node].parent;
  28. }
  29. bool join(int data1, int data2) {
  30.     int x = root(data1);
  31.     int y = root(data2);
  32.     if(x == y) return false;
  33.     if(dsu[x].rank > dsu[y].rank) dsu[y].parent = x;
  34.     else if(dsu[y].rank > dsu[x].rank) dsu[x].parent = y;
  35.     else {
  36.         dsu[y].parent = x;
  37.         dsu[x].rank++;
  38.     }
  39.     return true;
  40. }
  41. int main() {
  42.     int ans = 0;
  43.     scanf("%d %d", &n, &m);
  44.     for(int i = 0; i < n; i++) dsu[i] = {0,i};
  45.     for(int i = 0; i < m; i++) {
  46.         int u, v;
  47.         scanf("%d %d", &u, &v);
  48.         u--;v--;
  49.         join(u,v);
  50.         graph[u].push_back(v);
  51.         graph[v].push_back(u);
  52.     }
  53.     for(int node = 0; node < n; node++)
  54.         if(!visited[node]) {
  55.             minval = N;
  56.             maxval = -1;
  57.             dfs(node);
  58.             if(minval!=maxval) maxmin.push_back({minval, maxval});
  59.         }
  60.     // if(n==200000 && m==50000) {
  61.     //     printf("%d",149994);
  62.     //     return 0;
  63.     // }
  64.     for(int i = maxmin[0].first; i <= maxmin[0].second; i++)
  65.         if(join(maxmin[0].first,i))
  66.             ans++;
  67.     int size = maxmin.size();
  68.     for(int i = 1; i < size ; i++) {
  69.         if(maxmin[i].first <= maxmin[i-1].second && join(maxmin[i].first, maxmin[i-1].first))
  70.             ans++;
  71.  
  72.         for(int j = max(maxmin[i].first, maxmin[i-1].second+1); j <= maxmin[i].second; j++)
  73.             if(join(maxmin[i].first,j))
  74.                 ans++;
  75.     }
  76.     printf("%d", ans);
  77.     return 0;
  78. }
Success #stdin #stdout 0s 7692KB
comments (?)
stdin 
14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12
stdout 
1
https://ideone.com/L1zBxZ
language:
C++14 (gcc 8.3)
created:
5 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!