50分求助
查看原帖
50分求助
341122
lx503楼主2021/2/9 17:25
#include<bits/stdc++.h>
using namespace std;
int t;
int n;
struct yueshu
{
	int i,j,e;
}a[200001];
int fa[200001];
int level[200001];
map<int,int>m;
int maps;
void chu(int n)//初始化
{
	for(int i=1;i<=2*n;i++)
	{
		fa[i]=i;
		level[i]=1;
	}
}
int find(int x)
{
	if(fa[x]==x)return x;
	else return find(fa[x]);
}
void uni(int x,int y)//合并x和y所在的集合 
{
	
	int t1=find(x),t2=find(y);	
	if(level[x]<level[y])
	{
		fa[t1]=t2;
	}
	else if(level[x]>level[y])
	{
		fa[t2]=t1;
	}
	else
	{
		fa[t1]=t2;
		level[t2]++;
	}
}
bool cmp(yueshu x,yueshu y)
{
	return x.e>y.e;
}
void add(int x)
{
	if(!m[x])
	{
		maps++;
		m[x]=maps;
	}
	
}
int main()
{
//	freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		scanf("%d",&n);
		chu(n);
		bool can=1;
		maps=0;//共映射的数量 
		
		for(int j=1;j<=n;j++)
		{
			scanf("%d%d%d",&a[j].i,&a[j].j,&a[j].e);
			add(a[j].i);
			a[j].i=m[a[j].i];
			add(a[j].j);
			a[j].j=m[a[j].j];
		}
	/*	for(int j=1;j<=n;j++)
		{
			printf("%d %d %d\n",a[j].i,a[j].j,a[j].e);
		}*/
		sort(a+1,a+n+1,cmp);
		for(int j=1;j<=n;j++)
		{
			if(a[j].e==1)//相等 
			uni(a[j].i,a[j].j);
			else//不等 
			{
				if(find(a[j].i)==find(a[j].j))
				{
					can=0;
					break;
				}
			}
		}
		if(can)printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

1 还WA了2个点

2021/2/9 17:25
加载中...