Submission

Score: 100

User: exoworldgd

Problemset: Tech Sprites

Language: cpp

Time: 0.934 second

Submitted On: 2025-05-27 09:19:56

#include <bits/stdc++.h>
#define pii pair<int,int>
#define int long long
using namespace std;
const int MAX = 1e6+5;
int Min[MAX],Max[MAX],a[MAX];
struct dsu {
    vector<int> parent,sz;
    dsu(int n) {
    	parent.resize(n+1), sz.resize(n+1,1);
    	iota(parent.begin()+1,parent.end(),1);
	}
	int find(int x) {
		if (parent[x] != x) parent[x] = find(parent[x]);
		return parent[x];
	}
	bool unite(int x, int y) {
		x = find(x); y = find(y);
		if (x ==y) return 0;
		if (sz[x] < sz[y]) swap(x,y);
		parent[y] = x, sz[x] += sz[y];
		Min[x]=min(Min[y],Min[x]), Max[x]=max(Max[y],Max[x]);
		return 1;
	}
};
signed main(void) {
	cin.tie(nullptr)->sync_with_stdio(false),cout.tie(0);
	int n,m,cnt=0,mx=0;
    cin >> n >> m;
    dsu dsu(n);
    for(int i=1;i<=n;i++){
    	int x,y;
        cin >> x >> y;
        a[i]=(x*(int)1000000001)+y;
        Min[i]=Max[i]=a[i];
    }
    while (m--) {
    	int u,v;
    	cin >> u >> v;
    	dsu.unite(u,v);
	}
	vector<pii> ans;
	for (int i =1;i<=n ; i++) if (dsu.find(i) == i) ans.emplace_back(Min[i],Max[i]);
	sort(ans.begin(),ans.end());
	for (auto [l,r] : ans) {
		if (mx > l) cnt++;
		mx = max(mx,r);
	}
	cout << cnt;
}