fork download
copy 
  1. /* 
  2. Task: 1253D
  3. Date: Dec 19, 2020
  4. Written by aLittleLove (Minh Vu)
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8. #define rep(i,n) for (int i=0, _n=n; i<_n; i++)
  9. #define FOR(i,a,b) for (int _a=(a), _b=(b), i=_a; _a<=_b?i<=_b:i>=_b; _a<=_b?i++:i--)
  10. #define _mem(a, b) memset(a, (b), sizeof(a))
  11. #define pb push_back
  12. #define fi first
  13. #define se second
  14. #define sz(a) int((a).size())
  15.  
  16. using namespace std;
  17. typedef long long ll;
  18. typedef int64_t i64;
  19. typedef pair<int, int> pii;
  20. typedef vector<pii> vii;
  21. typedef vector<int> vi;
  22. const int N = 2e5 + 5;
  23. const int inf = 1e9;
  24. const int mod = 1e9 + 7;
  25. const double pi = atan(1) * 4.0;
  26. template<typename T, typename U> inline void mini(T &x, U y) { if(y < x) x = y; }
  27. template<typename T, typename U> inline void maxi(T &x, U y) { if(x < y) x = y; }
  28.  
  29. i64 _pow(i64 x, i64 y)
  30. {
  31.     if (y==0) return 1;
  32.     i64 tmp = _pow(x, y>>1ll);
  33.     if (y&1) return (tmp%mod * tmp%mod * x%mod)%mod;
  34.     return (tmp%mod * tmp%mod)%mod;
  35. }
  36.  
  37. vector<int> adj[N];
  38. bool vis[N];
  39. vector<pii> e;
  40.  
  41. int dfs(int u)
  42. {
  43.     int mx = u;
  44.     vis[u] = 1;
  45.     for (int v: adj[u])
  46.     {
  47.         if (!vis[v])
  48.         {
  49.             mx = max(mx, dfs(v));
  50.         }
  51.     }
  52.     return mx;
  53. }
  54.  
  55. void Solve()
  56. {
  57.     int n, m; cin >> n >> m;
  58.     int ans = 0;
  59.     rep(i,m)
  60.     {
  61.         int u, v; cin >> u >> v;
  62.         adj[u].pb(v);
  63.         adj[v].pb(u);
  64.     }
  65.     memset(vis,0,sizeof vis);
  66.     for (int i=1; i<=n; i++)
  67.         if (!vis[i]) e.pb({i, dfs(i)});
  68.     sort(e.begin(), e.end());
  69.     int j = 0;
  70.     for (int i=0; i<e.size() - 1; i++)
  71.     {
  72.         while (j<=i) ++j;
  73.         while (j<e.size() && e[j].fi <= e[i].se) ans++, j++;
  74.     }
  75.     cout << ans << '\n';
  76. }
  77.  
  78. int main()
  79. {
  80.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  81.     //freopen("input.txt","r",stdin);
  82.     int nTest; //cin >> nTest;
  83.     nTest = 1;
  84.     while (nTest--) Solve();
  85.  
  86.     return 0;
  87. }
Success #stdin #stdout 0s 8484KB
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/iBSA8K
Codeforces 1253D
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!