50pts求助
查看原帖
50pts求助
539133
q1uple楼主2022/9/27 13:32
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000100
int a[MAXN],b[MAXN],c[MAXN*2],ctop;
int d[MAXN*2],dtop;
int fa[MAXN*2];
int type[MAXN];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
int merge(int x,int y)
{
	x=find(x),y=find(y);
	if(x!=y)
		fa[x]=y;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		ctop=0,dtop=0; 
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i]>>b[i];
			cin>>type[i];
			c[++ctop]=a[i];
			c[++ctop]=b[i];
		}
		sort(c+1,c+ctop+1);
		for(int i=1;i<=ctop;i++)
		{
			if(c[i]!=c[i-1])
				d[++dtop]=c[i];
		}
		for(int i=1;i<=n;i++)
		{
			a[i]=lower_bound(d+1,d+dtop+1,a[i])-d;
			b[i]=lower_bound(d+1,d+dtop+1,b[i])-d;
		}
		for(int i=1;i<=dtop;i++)	fa[i]=1;
		for(int i=1;i<=n;i++)
		{
			if(type[i]==1)	
				merge(a[i],b[i]);
		}
		int qwq=1;
		for(int i=1;i<=n;i++)
		{
			if(type[i]==0)
			{
				if(find(a[i])==find(b[i])) 
				{
					qwq=0;
					break;
				}	
			}
		}
		if(qwq==1)
			cout<<"YES\n";
		else
			cout<<"NO\n";
	}
}
2022/9/27 13:32
加载中...