Submission

Score: 100

User: navysrimuang

Problemset: Tech Sprites

Language: cpp

Time: 0.565 second

Submitted On: 2026-04-10 21:15:41

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

int n,m;
vector<int> par,sz;

int find(int x){
    if(par[x] == x) return x;
    else return par[x] = find(par[x]);
}

bool unite(int a, int b){
    int ra = find(a);
    int rb = find(b);
    if(ra == rb) return 0;

    if(ra < rb) swap(ra,rb);
    par[rb] = ra;
    sz[ra] += sz[rb];
    return 1;
}

int main(){
    
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    par.resize(n+1);
    iota(par.begin(), par.end() , 0);
    sz.resize(n+1,1);
    vector<tuple<int,int,int>> iden; //a , b, id
    for(int i = 1;i<=n;i++){
        int a,b;
        cin >> a >> b;
        iden.push_back({a,b,i});
    }

    for(int i = 0;i<m;i++){
        int a,b;
        cin >> a >> b;
        unite(a,b);
    }

    sort(iden.begin() , iden.end());

    int cnt = 0;
    
    for(int i = 0;i<n;i++){
        auto [a,b,x] = iden[i];
        if(!i){
            sz[find(x)]--;
            continue;
        }

        auto [l,r,y] = iden[i-1];

        if(sz[find(y)] != 0 && unite(x,y)){
            cnt++;
        }

        sz[find(x)]--;
    }

    cout << cnt << "\n";
    
    return 0;
}