16求条
查看原帖
16求条
1375749
Green_Leaves楼主2024/10/24 18:30
#include<bits/stdc++.h>
#define ll long long
using namespace std;
pair<int,int> s[100005];
int fa[100005];
int find(int x){
	if(~fa[x])return fa[x]=find(fa[x]);
	return x;
}
int main(){
	ios::sync_with_stdio(0);
	int n;
	memset(fa,-1,sizeof(fa));
	cin>>n;
	for(int i=0;i<n;i++)cin>>s[i].first>>s[i].second;
	sort(s,s+n);
	vector<int> sets;
	sets.push_back(n-1);
	for(int i=n-2;i>=0;i--){
		while(sets.size()&&s[i].second<=s[find(sets.back())].second){
			fa[find(i)]=find(sets.back());
			sets.pop_back();
		}
		sets.push_back(i);
	}
	cout<<sets.size();
}
2024/10/24 18:30
加载中...