萌新求助20分
查看原帖
萌新求助20分
457431
Li_wenjie楼主2022/5/6 23:25
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+1;
int fa[N],a[N],nq[N][4],b[N];
int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
	int xx=find(x);
	int yy=find(y);
	if(xx!=yy)
		fa[xx]=yy;
}
int main()
{
//	freopen("p1955.in","r",stdin);
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		
		int top=0,_top=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d",&nq[i][1],&nq[i][2],&nq[i][3]);
			a[++top]=nq[i][1];
			a[++top]=nq[i][2];
		}
		sort(a+1,a+top+1);
		for(int i=1;i<=top;i++)
		if(a[i]!=a[i-1]) b[++_top]=a[i];
		int pd=1;
		for(int i=1;i<=_top;i++) fa[i]=i;
		for(int i=1;i<=n;i++)
		{
			int x=lower_bound(b+1,b+_top+1,nq[i][1])-b;
			int y=lower_bound(b+1,b+_top+1,nq[i][2])-b;
			if(nq[i][3]==1) merge(x,y);
			else
			{
				if(find(x)==find(y))
				{
					cout<<"NO"<<endl;
					pd=0;
				}
			}
		}
		if(pd)
		cout<<"YES"<<endl;
	}
}
2022/5/6 23:25
加载中...