Submission

Score: 100

User: Xapitize

Problemset: Tech Sprites

Language: cpp

Time: 0.636 second

Submitted On: 2026-03-20 20:45:07

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

#define ll long long
#define all(x) (x).begin(), (x).end()

vector<int> parent(1e6+2);

int findRoot(int u)
{
    if(parent[u]==u) return u;
    return parent[u] = findRoot(parent[u]);
}

void uni(int u, int v)
{
    if(findRoot(u) != findRoot(v))
    {
        parent[findRoot(u)] = parent[findRoot(v)];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    vector<pair<int,int>> spirits(n+1); // shy , spark
    spirits[0] = {0,0};
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin >> a >> b;
        spirits[i] = {a,b};
    }
    for(int i=1;i<=n;i++)
    {
        parent[i]=i;
    }
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin >> x >> y;
        uni(x,y);
    }
    vector<pair<pair<int,int>,int>> group;
    vector<int> groupcount(1e6+2,0);
    vector<bool> connectedgroup(n+1,false);
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        group.emplace_back(spirits[i],findRoot(i));
        groupcount[findRoot(i)]++;
    }
    sort(all(group));
    // for(int i=1;i<=n;i++)
    // {
    //     cout << group[i-1].second << " ";
    // }
    // cout << "\n";
    for(int i=1;i<=n-1;i++)
    {
        groupcount[findRoot(group[i-1].second)]--;
        if(findRoot(group[i-1].second)!=findRoot(group[i].second) && groupcount[findRoot(group[i-1].second)]>=1)
        {
            groupcount[findRoot(group[i-1].second)] = groupcount[findRoot(group[i-1].second)]+groupcount[findRoot(group[i].second)];
            groupcount[findRoot(group[i].second)] = 0;
            uni(group[i].second,group[i-1].second);
            // for(int i=1;i<=n;i++)
            // {
            //     cout << findRoot(group[i-1].second) << " ";
            // }
            // cout << "\n";
            ans++;
        }
    }
    cout << ans;
    // for(int i : subgroup)
    // {
    //     sort(all(group[i]));
    // }
    // for(int i : subgroup)
    // {
    //     bool stop = false;
    //     for(int j=0;j<group[i].size();j++)
    //     {
    //         if(!st.empty())
    //         {
    //             while(stop==false)
    //             {
    //                 if(st.empty()) stop=true;
    //                 else if(group[i][j].first<st.top().first.first)
    //                 {
    //                     stop = true;
    //                 }
    //                 else if(group[i][j].first==st.top().first.first && group[i][j].second < st.top().first.second)
    //                 {
    //                     stop = true;
    //                 }
    //                 else
    //                 {
    //                     if(poppedgroup[st.top().second]==false)
    //                     {
    //                         ans++;
    //                         poppedgroup[st.top().second] = true;
    //                     }
    //                     st.pop();
    //                 }
    //             }
    //         }
    //         st.push({group[i][j],i});
    //     }
    // }
    return 0;
}