SHARE
TWEET

Untitled

a guest Dec 8th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl        '\n'
  5. #define pb push_back
  6. const int MAXN    = 2e5+9;
  7. /*-----------------------------------------------------------------------------------------------------*/
  8.  
  9. int pa[MAXN], sz[MAXN];
  10. int fnd(int x) {return(x==pa[x]?x:pa[x]=fnd(pa[x]));}
  11. bool uni(int a, int b) {
  12.     if((a=fnd(a))==(b=fnd(b))) return false;
  13.     if(sz[a]>sz[b]) swap(a, b);
  14.     pa[a]=b; sz[b]+=sz[a];
  15.     return true;
  16. }
  17. //O(mlogn+nlogn)
  18. int main() {
  19.     ios::sync_with_stdio(0); cin.tie(NULL);
  20.  
  21.     for(int i = 0; i < MAXN; i++) pa[i]=i, sz[i]=1;
  22.     int n, m, a, b, ans=0, nm=0, cur;
  23.     cin >> n >> m;
  24.     vector<int> edge[MAXN];
  25.     for(int i = 0; i <m; i++) {
  26.         cin >> a >> b;
  27.         if(a>b) swap(a, b);
  28.         edge[a].pb(b);
  29.         uni(a, b);
  30.     }//O(mlogn)
  31.  
  32.     for(int i = 1; i <= n; i++) {
  33.         cur=0;
  34.         for(int x: edge[i]) {
  35.             cur=max(cur, x);
  36.         }//O(n+m)
  37.         if(cur==0) continue;
  38.         for(int j = cur; j> max(nm, i); j--) {
  39.             if(uni(i, j)) {
  40.                 ans++;
  41.             }
  42.         }//O(n+nlogn)
  43.         if((nm=cur)==n) break;
  44.     }
  45.     cout << ans <<endl;
  46.  
  47.     return 0;
  48. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top