• API
• FAQ
• Tools
• Archive
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.

Top