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