Submission

Score: 100

User: kungarooo

Problemset: Tech Sprites

Language: cpp

Time: 1.463 second

Submitted On: 2025-11-01 14:37:51

#include<bits/stdc++.h>
using namespace std;
int csz=0;
vector<vector<int>> adj(1000001);
tuple<int,int,int> p[1000001];
vector<bool> vis(1000001,false);
void dfs(int node,int& g){
    if(vis[node])return;
    vis[node]=1;
    csz++;
    //cout<<node<<"::\n";
    auto [a,b,gg]=p[node];
    p[node]={a,b,g};
    for(auto i:adj[node]){
        if(vis[i])continue;
        dfs(i,g);
    }
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int u,v;
        cin>>u>>v;
        p[i]={u,v,-1};
    }
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u-1].push_back(v-1);
        adj[v-1].push_back(u-1);
    }
    int cnt=1;
    vector<int> gsz;
    gsz.push_back(0);
    for(int i=0;i<n;i++){
        auto [a,b,g]=p[i];
        if(g==-1){
            csz=0;
            //cout<<i<<":\n";
            dfs(i,cnt);
            gsz.push_back(csz);
            cnt++;
        }
    }
    int par[cnt]={};
    bool found[cnt]={};
    int ans=0,counter=0;
    for(int i=0;i<cnt;i++){
        par[i]=i;
    }
    sort(p,p+n);
    for(int i=0;i<n;i++){
        auto [a,b,g]=p[i];
        if(counter==0){
            counter+=gsz[g];
            found[g]=1;
            counter--;
            continue;
        }
        if(!found[g]){
            ans++;
            counter+=gsz[g];
            found[g]=1;
        }
        counter--;
    }
    cout<<ans;
    return 0;
}