Submission

Score: 100

User: foldnut

Problemset: Tech Sprites

Language: cpp

Time: 0.585 second

Submitted On: 2025-11-10 22:25:46

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int mxN = 1e6 + 5;
vector<pii> a(mxN);
int p[mxN], s[mxN]; pii mx[mxN], mn[mxN];
int _find(int x){
    if(x == p[x]){
        return x;
    }
    return p[x] = _find(p[x]);
}
void _union(int x, int y){
    int X = _find(x), Y = _find(y);
    if(X != Y){
        if(s[X] < s[Y]){
            swap(X, Y);
        }
        s[X] += s[Y];
        p[Y] = X;
        mn[X] = min(mn[X], mn[Y]);
        mx[X] = max(mx[X], mx[Y]);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    for(int i = 0;i<n;i++){
        cin >> a[i].first >> a[i].second;
    }
    for(int i = 1;i<=n;i++){
        p[i] = i;
        mx[i] = a[i - 1];
        mn[i] = a[i - 1];
        s[i] = 1;
    }
    for(int i = 0;i<m;i++){
        int u, v;
        cin >> u >> v;
        _union(u, v);
    }
    vector<pair<pii, pii>> g;
    for(int i = 1;i<=n;i++){
        if(_find(i) == i){
            g.push_back({mn[i], mx[i]});
        }
    }
    sort(g.begin(), g.end());
    int ans = 0;
    pii nw = g[0].second;
    for(int i = 1;i<g.size();i++){
        if(g[i].first < nw) ++ans;
        nw = max(nw, g[i].second);
    }
    cout << ans;
}