Submission

Score: 100

User: meme_boi2

Problemset: Tech Sprites

Language: cpp

Time: 0.600 second

Submitted On: 2025-08-14 08:18:49

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define tii tuple<int,int,int>
vector<int> pa(1e6+1),cnt(1e6+1,1);
vector<tii> mat;
int ans,n,m,cut;
int find(int i){
    if(pa[i] == i) return i;
    else return pa[i] = find(pa[i]);
}
void U(int u,int v){
 //   u = find(u);
   // v= find(v);
    if(u == v) pa[u] = v;
    else if(u > v) {pa[u] = v; cnt[v] += cnt[u];}
    else {pa[v] = u; cnt[u] += cnt[v];} 
   // cout << "Union " << max(cnt[u],cnt[v]) << '\n';
}
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin >> n >> m;
    mat.resize(n);
    for(int i = 1; i <= n; i++){
        int a, b;
        cin >>a >> b;
        pa[i] = i;
        mat[i-1] = {a,b,i};
    }
    sort(mat.begin(),mat.end());
    while(m--){
        int u, v;
        cin >> u >> v;
       // cnt[u]++;
        //cnt[v]++;
        u = find(u); v = find(v);
        U(u,v);
    }
    //cut = 1;
    // cout << find(7) << ' ' << find(1) <<  " BRUH\n";
    for(int j = 0; j < n-1; j++){
        int u = get<2>(mat[j]), v = get<2>(mat[j+1]);
        if(find(u) != find(v)){
            if(cnt[find(u)] > 1){
               // cout << u << ' ' << v << ' ' << cnt[find(u)] << '\n';
                 ans += 1;
              //  cout << u << ' ' << v << ' '  << find(u) << " " << find(v) << ' '<< cut <<' ' << cnt[find(u)] <<" NIG \n";
               // cut += cnt[find(v)];
                U(find(u),find(v));
            }
        }
        cnt[find(u)]--;
      //  cut++;
    }
   
    cout << ans;
}