并查集+离散化60分求助
查看原帖
并查集+离散化60分求助
224192
蒟蒻且菜鸡楼主2021/8/22 16:46
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct node{
	int x,y;
}a[1000000];
int n,m,top;
int c[1000000],b[10000000],e[1000000],fa[10000000];
int search(int x)
{
	int l=1,r=m,mid;
	while(l+1<r)
	{
		mid=(l+r)>>1;
		(c[mid]<=x?l:r)=mid;
	}
	return c[l]==x?l:r;
}
int find(int x){return fa[x]=x==fa[x]?x:find(fa[x]);}
void merge(int x,int y)
{
	int fx=find(x),fy=find(y);
	if(fx!=fy) fa[fx]=fy;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		bool flag=true;
		cin>>n;
		memset(fa,0,sizeof(fa));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		for(int k=1;k<=n;k++)
		{
			cin>>a[k].x>>a[k].y>>e[k];
			b[++top]=a[k].x;
			b[++top]=a[k].y;
		}
		sort(b+1,b+top+1);
		for(int i=1;i<=top;i++)
	 	  if(i==1||b[i]!=b[i-1])
			c[++m]=b[i];
		for(int i=1;i<=n;i++)
		  a[i].x=search(a[i].x),a[i].y=search(a[i].y);
		for(int i=1;i<=m;i++)
		  fa[i]=i;
		sort(e+1,e+n+1);
		for(int i=n;i>=1;i--)
		{
			if(e[i]) merge(a[i].x,a[i].y);
			else
			{
				if(find(a[i].x)==find(a[i].y))
				{
					flag=false;
					break;	
				}
			}
		}
		if(flag) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}
2021/8/22 16:46
加载中...