离散加并查集,不知道错哪了QwQ
查看原帖
离散加并查集,不知道错哪了QwQ
826007
Arrogant666666楼主2023/3/4 19:38
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define maxn 200010
#define base 261

int fa[1000010];
int t,n,num,num1,num2,len;
pair<int,int> p[1000010],q[1000010];
int tmp[3000010];

int Find(int x){
	return x==fa[x]?fa[x]:fa[x]=Find(fa[x]);
}

int main(){
	cin>>t;
	while(t--){
		cin>>n;
		num=num1=num2=0;
		memset(fa,0,sizeof(fa));
		for(int i=1;i<=n;i++){
			int a,b,c;
			cin>>a>>b>>c;
			if(c==1){
				tmp[++num1]=a;
				tmp[++num1]=b;
				q[++num].first=a;
				q[num].second=b;
			}
			if(c==0){
				p[++num2].first=a;
				p[num2].second=b;
			}
		}
		sort(tmp+1,tmp+num1+1);
		len=unique(tmp+1,tmp+num1+1)-tmp;
		for(int i=0;i<=len+1;i++)fa[i]=i;
		for(int i=1;i<=num;i++){
			q[i].first=lower_bound(tmp+1,tmp+len,q[i].first)-tmp;
			q[i].second=lower_bound(tmp+1,tmp+len,q[i].second)-tmp;
			int x=Find(q[i].first);
			int y=Find(q[i].second);
			fa[y]=x;
		}
		bool bo=0;
		for(int i=1;i<=num2;i++){
			int x=Find(p[i].first);
			int y=Find(p[i].second);
			if(x==y){
				bo=1;
				cout<<"NO"<<endl;
				break;
			}
		}
		if(!bo)cout<<"YES"<<endl;
	}
}
2023/3/4 19:38
加载中...