连边的点用并查集检查是否有环，如果他们的fa是同一个点说明绕了一圈绕回去了。n个点一共能连n-1条边，如果小于n-1条边说明存在多个联通块。
1 #define HAVE_STRUCT_TIMESPEC 2 #include<bits/stdc++.h> 3 using namespace std; 4 int a[500007],b[500007]; 5 int u[1000007]; 6 int v[1000007]; 7 int fa[500007]; 8 int find_(int x){ 9 if(fa[x]==x) 10 return x; 11 return fa[x]=find_(fa[x]); 12 } 13 set<int>st; 14 int main(){ 15 ios::sync_with_stdio(false); 16 cin.tie(NULL); 17 cout.tie(NULL); 18 int n; 19 cin>>n; 20 for(int i=1;i<=n;++i) 21 fa[i]=i; 22 for(int i=1;i<=n;++i){ 23 cin>>a[i]>>b[i]; 24 u[a[i]]=i; 25 v[b[i]]=i; 26 } 27 int cnt=0; 28 int temp=0; 29 for(int i=1;i<=2*n;++i){ 30 if(u[i]){ 31 temp=u[i]; 32 for(auto it:st){ 33 if(it>b[u[i]]){ 34 break; 35 } 36 else{ 37 int x=find_(v[it]); 38 int y=find_(temp); 39 if(x!=y){ 40 ++cnt; 41 fa[x]=y; 42 } 43 else{ 44 cout<<"NO "; 45 return 0; 46 } 47 } 48 } 49 st.insert(b[u[i]]); 50 } 51 else{ 52 temp=v[i]; 53 st.erase(st.find(b[v[i]])); 54 } 55 } 56 if(cnt==n-1) 57 cout<<"YES "; 58 else 59 cout<<"NO "; 60 return 0; 61 }