Submission

Score: 100

User: NovemNotes

Problemset: Tech Sprites

Language: cpp

Time: 0.633 second

Submitted On: 2026-04-24 15:20:52

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+2;

struct stc{
    int a,b,c,d;
};

int n,m,gp,ans=0;
vector<pair<int,int>> v;
int head[N];
int grp[N];
vector<pair<int,int>> vp[N];
vector<stc> pv;

int findhead(int n){
    return head[n]==n? n:head[n]=findhead(head[n]);
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> m;v.resize(n+1);gp=n;
    for(int i=1;i<=n;i++)head[i]=i;
    for(int i=1;i<=n;i++){
        cin >> v[i].first >> v[i].second;
    }
    while(m--){
        int a,b;cin >> a >> b;
        int ha=findhead(a),hb=findhead(b);
        if(ha==hb)continue;
        head[ha]=hb;
        gp--;
    }
    int g=0;
    for(int i=1;i<=n;i++){
        int hi = findhead(i);
        if(!grp[hi]){
            grp[i]=grp[hi]=++g;
        }else{
            grp[i]=grp[hi];
        }
        vp[grp[i]].emplace_back(v[i]);
    }
    for(int i=1;i<=gp;i++){
        sort(vp[i].begin(),vp[i].end(),[](const pair<int,int> &a,const pair<int,int> &b){
            if(a.first==b.first)return a.second<b.second;
            return a.first<b.first;
        });
        int np = vp[i].size();
        pv.push_back({vp[i][0].first,vp[i][0].second,vp[i][np-1].first,vp[i][np-1].second});
    }
    sort(pv.begin(),pv.end(),[](const stc &a,const stc&b){
        if(a.a==b.a)return a.b < b.b;
        return a.a < b.a;
    });
    pair<int,int> last;
    for(int i=0;i<pv.size();i++){
        auto [a,b,c,d]=pv[i];
        // cout << "("<<a<<","<<b<<") ("<<c<<","<<d<<")\n";
        if(i==0)last={c,d};
        else{
            if(a<last.first||(a==last.first && b<last.second)){
                ans++;
                if(c>last.first||(c==last.first && d>last.second)){
                    last={c,d};
                }
            }else{
                last = {c,d};
            }
        }
    }
    cout << ans << "\n";
    return 0;
}