Submission

Score: 40

User: njoop

Problemset: Tech Sprites

Language: cpp

Time: 0.382 second

Submitted On: 2025-05-23 17:53:55

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define MAXN 200005
#define MOD (int)(1e9+7)
#define INF (int)1e17
#define enl '\n'
#define int long long
#define DB(code) cout<<'\t'<<code<<'\n';
#define SP <<' '<<
using namespace std;
int par[MAXN],sz[MAXN];
int root(int cur){
    return par[cur]=(par[cur]==cur)?cur:root(par[cur]);
}
void join(int a,int b){
    if(sz[a]>=sz[b]){
        par[b]=a;
        sz[a]+=sz[b];
    } else{
        par[a]=b;
        sz[b]+=sz[a];
    }
}
int n,m;
int arr[MAXN];
vector<int> graph[MAXN];
vector<int> cmp;
bool vis[MAXN];
void dfs(int cur){
    cmp.pb(arr[cur]);
    vis[cur]=true;
    for(auto v: graph[cur]) if(!vis[v]) dfs(v);
}
signed main(){
    int u,v;
	cin >> n >> m;
	for(int i=0; i<n; i++){
        cin >> u >> v;
        arr[i]=(u-1)*(int)1e9+(v-1);
	}
	for(int i=0; i<m; i++){
	    cin >> u >> v;
	    u--; v--;
	    graph[u].pb(v);
	    graph[v].pb(u);
	}
	vector<pii> num;
	vector<int> cmpsz;
	int t=0;
	for(int i=0; i<n; i++) if(!vis[i]){
	    cmp.clear();
	    dfs(i);
	    cmpsz.pb(cmp.size());
	    num.pb({cmp[0],t});
	    for(int j=1; j<cmp.size(); j++) num.pb({cmp[j],t});
	    t++;
	}
	sort(num.begin(),num.end());
	for(int i=0; i<t; i++){
	    par[i]=i;
	    sz[i]=1;
	}
	int rem=0,now,ans=0;
	for(auto p: num){
	    if(rem==0){
	        now=p.s;
	        rem=cmpsz[p.s];
	    } else{
	        int a=root(now),b=root(p.s);
	        if(a!=b){
	            rem+=cmpsz[p.s];
	            join(a,b);
	            ans++;
	        }
	    }
	    rem--;
	}
	cout << ans;
	return 0;
}

/*

5 2
10 20 30 40 50
1 3
2 4

5 1
50 40 30 20 10
1 5

*/