Submission

Score: 100

User: nozmid

Problemset: Tech Sprites

Language: cpp

Time: 1.389 second

Submitted On: 2025-06-08 04:32:49

#include<bits/stdc++.h>

#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx2")

using namespace std;

#define emb emplace_back
#define em emplace
#define pb push_back
#define ph push

struct stc{
	int a, b, g;
	bool operator<(const stc &x) const{
		if(a != x.a) return a < x.a;
		return b < x.b;
	}
};

struct DSU{
	vector<int> pa, sz, gr;
	DSU(int n){
		pa.resize(n);
		sz.assign(n, 1);
		gr.resize(n);
		iota(pa.begin(), pa.end(), 0);
	}
	int findset(int u){
		if(pa[u] == u) return u;
		return pa[u] = findset(pa[u]);
	}
	void unite(int u, int v){
		u = findset(u);
		v = findset(v);
		if(u == v) return;
		if(sz[v] > sz[u]) swap(u, v);
		gr[u] += gr[v];
		sz[u] += sz[v];
		pa[v] = u;
	}
};

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m;
	cin >> n >> m;
	DSU dsu(n+1);
	stc tech[n+1];
	vector<int> adj[n+1];
	bool vis[n+1] = {};
	queue<int> qu;
	for(int i=1;i<=n;++i){
		cin >> tech[i].a >> tech[i].b;
	}
	for(int i=0;i<m;++i){
		int u, v;
		cin >> u >> v;
		adj[u].emb(v);
		adj[v].emb(u);
	}
	int cnt = 0;
	for(int i=1;i<=n;++i){
		if(vis[i]) continue;
		++cnt;
		vis[i] = 1;
		qu.em(i);
		while(!qu.empty()){
			int u = qu.front();
			qu.pop();
			tech[u].g = cnt;
			++dsu.gr[cnt];
			for(int v : adj[u]){
				if(!vis[v]){
					vis[v] = 1;
					qu.em(v);
				}
			}
		}
	}
	sort(tech+1, tech+n+1);
	int tmp = tech[1].g, res = 0;
	for(int i=1;i<=n;++i){
		int g = tech[i].g;
		if(!dsu.gr[tmp]) tmp = g;
		if(dsu.findset(tmp) != dsu.findset(g)){
			dsu.unite(tmp, g);
			++res;
		}
		--dsu.gr[tmp];
	}
	cout << res;
}