P1955 90pts 悬关 WA2
查看原帖
P1955 90pts 悬关 WA2
907113
Bug_Hunter楼主2024/7/7 16:00
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t,n,x[N],y[N],e[N],s[N*2],cnt,tmp,f[N];
map<int,int>mp;
int find(int x){
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
int main(){
	cin>>t;
	while(t--){
		mp.clear();
		memset(f,0,sizeof(f));
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		memset(e,0,sizeof(e));
		memset(s,0,sizeof(s));
		cin>>n;
		cnt=0;
		for(int i=1;i<=n;i++){
			cin>>x[i]>>y[i]>>e[i];
			s[++cnt]=x[i];
			s[++cnt]=y[i];
		}
		sort(s+1,s+1+cnt);
		tmp=0;
		for(int i=1;i<=cnt;i++){
			if(s[i]>s[i-1]){
				mp[s[i]]=++tmp;
			}
		}
		for(int i=1;i<=n;i++){
			x[i]=mp[x[i]];
			y[i]=mp[y[i]];
		}			//离散化 
		for(int i=1;i<=cnt;i++){
			f[mp[s[i]]]=mp[s[i]];
		}
		for(int i=1;i<=n;i++){
			if(e[i]==1){
				f[find(x[i])]=find(y[i]);
			}
		}
		bool flag=0;
		for(int i=1;i<=n;i++){
			if(e[i]==0){
				int fx=find(x[i]),fy=find(y[i]);
				if(fx==fy){
					cout<<"NO"<<endl;
					flag=1;
					break;
				}
			}
		}
		if(!flag) cout<<"YES"<<endl;
	}
	return 0;
}
2024/7/7 16:00
加载中...