Submission

Score: 100

User: KantaponZ

Problemset: Tech Sprites

Language: cpp

Time: 2.101 second

Submitted On: 2025-06-11 13:09:40

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

int n, m;
vector<tuple<int,int,int>> v;
vector<int> order(1000002), num(1000001);
int pa[1000001];

int fp(int n) {
    if (pa[n] == n) {
        return n;
    }
    return pa[n] = fp(pa[n]);
}


int main() {
    ios_base::sync_with_stdio(), cin.tie(0);
    cin >> n >> m;
    if (n == 1) {
        cout << 0;
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a,b,i});
        pa[i] = i;
    }
    sort(v.begin(), v.end());
    for (int i = 1; i <= n; i++) {
        auto [a, b, x] = v[i-1];
        order[i] = x;
        //cout << x << " ";
    }
    //cout << endl;
    
    while (m--) {
        int u, v;
        cin >> u >> v;
        int pu = fp(u), pv = fp(v);
        if (pu != pv) {
            pa[pu] = pv;
        }
    }
    for (int i = 1; i <= n; i++) {
        num[fp(i)]++;
    }
    num[fp(order[1])]--;
    //cout << num[fp(order[0])] << endl;
    int ct = 0;
    for (int a = 2; a <= n; a++) {
        int x = order[a - 1];
        int i = order[a];
        int px = fp(x), pi = fp(i);
        if (px == pi) {
            num[pi]--;
            continue;
        }
        if (num[px] <= 0) {
            num[pi]--;
            continue;
        }
        if (px != pi && num[px] > 0) {
            pa[pi] = px;
            num[px] += num[pi] - 1;
            num[pi] = 0;
            ct++;
        }
    }
    cout << ct;
}