Submission

Score: 23

User: nozmid

Problemset: Tech Sprites

Language: cpp

Time: 1.369 second

Submitted On: 2026-04-23 21:22:28

#include <bits/stdc++.h>

using namespace std;

#define emb emplace_back

struct stc{
	int g, f, s;
	bool operator<(const stc &o) const{
		if(f != o.f) return f < o.f;
		return s < o.f;
	}
};

const int maxn = 1e6 + 5;

int n, m;
stc arr[maxn];
vector<int> adj[maxn];
bool vis[maxn];
int gcnt, cnt[maxn];
int pa[maxn];
stack<int> stk;
int res;

int findset(int u){
	if(u == pa[u]) return u;
	return pa[u] = findset(pa[u]);
}

void dfs(int u){
	arr[u].g = gcnt;
	for(auto e : adj[u]){
		if(vis[e]) continue;
		vis[e] = 1;
		dfs(e);
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;++i){
		cin >> arr[i].f >> arr[i].s;
	}
	for(int i=0;i<m;++i){
		int u, v;
		cin >> u >> v;
		adj[u].emb(v);
		adj[v].emb(u);
	}
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			++gcnt;
			vis[i] = 1;
			dfs(i);
		}
	}
	sort(arr+1, arr+1+n);
	iota(pa, pa+maxn, 0);
	//for(int i=1;i<=n;++i) cout << arr[i].g << " ";
	for(int i=1;i<=n;++i){
		int u = arr[i].g, pu = findset(u);
		if(cnt[u] > 0){
			while(cnt[u]){
				int v = stk.top();
				stk.pop();
				--cnt[v];
				v = findset(v);
				if(pu != v){
					pa[v] = pu;
					++res;
				}
			}
		}
		stk.push(u);
		++cnt[u];
	}
	cout << res;
}