Submission

Score: 100

User: Dormon

Problemset: Tech Sprites

Language: cpp

Time: 0.730 second

Submitted On: 2025-05-27 21:42:08

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
using pii = pair<int, int>;

vector<int> pa;

struct A {
    int a, b, i;
    bool operator < (const A &o) const {
        if (a != o.a) return a < o.a;
        return b < o.b;
    }
};

class DSU {
public:
    vector<int> pa, sz;
    int n;
    DSU(int n){
        pa.resize(n + 1);
        sz.assign(n + 1, 1);
        this->n = n + 1;
        iota(pa.begin(), pa.end(), 0);
    }
    int f(int i){
        if (pa[i] == i) return i;
        return pa[i] = f(pa[i]);
    }

    bool untie(int u, int v){
        int fu = f(u), fv = f(v);
        if (fu == fv) return false;
        if (sz[fu] > sz[fv]) swap(fu, fv);
        pa[fu] = fv;
        sz[fv] += sz[fu];
        sz[fu] = 0;
        return true;
    }
};  

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    DSU dsu(n);
    vector<A> v(n + 1);
    for (int i = 1;i <= n;i++){
        int a, b;
        cin >> a >> b;
        v[i] = {a, b, i};
    }

    sort(v.begin() + 1, v.end());

    for (int i = 0;i < m;i++){
        int u, v;
        cin >> u >> v;
        dsu.untie(u, v);
    }

    int ans = 0;

    for (int i = 0;i < n - 1;i++){
        int compo = dsu.f(v[i].i), ncompo = dsu.f(v[i + 1].i);
        dsu.sz[compo]--;
        if (compo != ncompo){
            ans += (dsu.sz[compo] != 0);
            dsu.untie(compo, ncompo);
        }
    }

    cout << ans << '\n';

}