Educational Codeforces Round 78 (Rated for Div. 2)D(并查集+SET)

时间:2023-01-31 15:27:56

连边的点用并查集检查是否有环,如果他们的fa是同一个点说明绕了一圈绕回去了。n个点一共能连n-1条边,如果小于n-1条边说明存在多个联通块。

 #define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int a[],b[];
int u[];
int v[];
int fa[];
int find_(int x){
if(fa[x]==x)
return x;
return fa[x]=find_(fa[x]);
}
set<int>st;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
for(int i=;i<=n;++i)
fa[i]=i;
for(int i=;i<=n;++i){
cin>>a[i]>>b[i];
u[a[i]]=i;
v[b[i]]=i;
}
int cnt=;
int temp=;
for(int i=;i<=*n;++i){
if(u[i]){
temp=u[i];
for(auto it:st){
if(it>b[u[i]]){
break;
}
else{
int x=find_(v[it]);
int y=find_(temp);
if(x!=y){
++cnt;
fa[x]=y;
}
else{
cout<<"NO\n";
return ;
}
}
}
st.insert(b[u[i]]);
}
else{
temp=v[i];
st.erase(st.find(b[v[i]]));
}
}
if(cnt==n-)
cout<<"YES\n";
else
cout<<"NO\n";
return ;
}