Submission

Score: 100

User: friendlyjohala

Problemset: Tech Sprites

Language: cpp

Time: 0.603 second

Submitted On: 2026-04-21 21:49:03

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

using tp=tuple<int,int,int>;
const int N=1e6+5;
int parent[N],sz[N];
int n,m,cnt;

bool cmp(const tp &l,const tp &r){
    auto [al,bl,il]=l; auto [ar,br,ir]=r;
    if(al!=ar) return al<ar;
    else return bl<br;
}

int findSet(int u){
    if(parent[u]==u) return u;
    else return parent[u]=findSet(parent[u]);
}

void unionSet(int u,int v){
    int U=findSet(u);
    int V=findSet(v);

    //want sz[V]<=sz[U]
    if(sz[U]<sz[V]) swap(U,V);

    parent[V]=U;
    sz[U]+=sz[V];
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    
    cin>>n>>m;
    for(int i=1;i<=n;i++) { parent[i]=i; sz[i]=1; }
    //cout<<n<<" "<<m<<endl;
    vector<tp> ts;
    for(int i=1;i<=n;i++){
        int a,b; cin>>a>>b;
        ts.push_back({a,b,i});

        //cout<<a<<" "<<b<<" "<<i<<endl;
    }

    sort(ts.begin(),ts.end(),cmp);

    for(int i=0;i<m;i++){
        int u,v; cin>>u>>v;
        if(findSet(u)!=findSet(v)){
            unionSet(u,v);
        }
    }

    for(int i=1;i<n;i++){
        auto [a1,b1,u]=ts[i-1]; auto [a2,b2,v]=ts[i];
        
        int U=findSet(u); int V=findSet(v);
        if(U==V){
            sz[U]--;
        }
        else if(sz[U]==1){
            parent[U]=V;
        }
        else{ //findSet(u)!=findSet(v) && sz[U]>1
            parent[U]=V;
            sz[V]+=sz[U]-1;
            cnt++;
        }
    }

    cout<<cnt<<endl;
}