40分,并查集+离散化,找不出自己哪里错了
查看原帖
40分,并查集+离散化,找不出自己哪里错了
181805
天马行空mz楼主2023/2/11 19:32
#include<bits/stdc++.h>
using namespace std;
#define maxn 2000100
#define ll long long
int shangji[maxn];//上级
int gd[maxn];//树的高度
unordered_map<int,int> pd;
struct fa
{
	int i,j,e; 
}f[maxn];
bool cmp(fa a,fa b)
{
	return a.e>b.e;
}
void init(int n)//初始化
{
    for(int i=0;i<n;i++)
    {
        shangji[i]=i;//每个结点的上级都是自己
        gd[i]=1;
    }
}
int find(int x)//查找结点x的根节点,同时完成路径压缩,让上级指向最上级。
{
    if(shangji[x]==x)//当他等于他本身的时候,他最大。
        return x;//返回它本身
    return shangji[x]=find(shangji[x]);//不断递归完成压缩,使每个数指向最大上级。
}
bool join(int x,int y)
{
    x=find(x);//找到x的上级
    y=find(y);//找到y的上级
    if(x==y)
        return false;
    if(gd[x]>gd[y])//如果x高度大于y,则令y的上级为x
        shangji[y]=x;//让y的上级为x
    else
    {
        if(gd[x]==gd[y])
            gd[y]++;
        shangji[x]=y;//让x的上级为y
    }
    return true;
}
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--)
	{
		int ans=0;
		memset(&f,0,sizeof(struct fa));
		pd.clear();
		int sum=0;
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>f[i].i>>f[i].j>>f[i].e;
			if(pd[f[i].i]==0)
			{
				f[i].i=++sum;
				pd[f[i].i]=sum;
			}
			else f[i].i=pd[f[i].i];
			if(pd[f[i].j]==0)
			{
				f[i].j=++sum;
				pd[f[i].j]=sum;
			}
			else f[i].j=pd[f[i].j];			
		}
		init(sum);
		sort(f+1,f+n+1,cmp);
		for(int i=1;i<=n;i++)
		{
			if(f[i].e==0&&find(f[i].i)==find(f[i].j))
			{
				 ans=1;
				 break;
			}
			else if(f[i].e==1) join(f[i].i,f[i].j);
		}
		if(ans==0) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
} 
2023/2/11 19:32
加载中...