Submission

Score: 0

User: .n0t_gloomy.

Problemset: Tech Sprites

Language: cpp

Time: 2.607 second

Submitted On: 2026-03-12 15:53:03

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define n0t_gloomy ios_base::sync_with_stdio(false); cin.tie(nullptr);
int findpar(int n, vector<int> &par)
{
    if (n == par[n]) return n;
    return par[n] = findpar(par[n],par);
}
signed main()
{
    n0t_gloomy;
    int n,m;
    cin>>n>>m;

    map<int,pii> old;
    map<pii,int> newmap;
    vector<pii> v(n);
    
    for (int i = 0; i < n; i++)
    {
        int a,b;
        cin>>a>>b;
        pii tmp = {a,b};
        old[i] = tmp;
        v[i] = tmp;
    }
    sort(v.begin(),v.end());
    for (int i = 0; i < n; i++)
    {
        newmap[v[i]] = i;
    }
    vector<vector<int>> adj(n);
    vector<int> par(n);
    iota(par.begin(),par.end(),0);
    for (int i = 0; i < m; i++)
    {
        int u,v;
        cin>>u>>v;
        u--; v--;
        pii tmp = old[u];
        int newu = newmap[tmp];
        tmp = old[v];
        int newv = newmap[tmp];
        adj[newu].push_back(newv);
        adj[newv].push_back(newu);
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < adj[i].size(); j++)
        {
            int ru = findpar(i,par);
            int rv = findpar(adj[i][j],par);
            if (ru != rv) par[rv] = ru;
        }
    }
    // cout<<"parents : ";
    // for (auto it : par) cout<<it<<" ";
    // cout<<"\n";
    int ans = 0;
    set<int> st;
    for (int i = 0; i < n; i++)
    {
        st.insert(findpar(i, par));
    }
    for (int i = 0; i < n-1; i++)
    {
        if (par[i] != par[i+1]) ans++;
    }
    cout<<ans-st.size()+1<<"\n";
}