求助大佬,扩展域并查集为什么90分?
查看原帖
求助大佬,扩展域并查集为什么90分?
631052
ysw0521nb楼主2022/11/16 13:12
#include<bits/stdc++.h>
using namespace std;
const int N=1000500;
int f,n;
int t;
int fa[N*2];
int o[N],p[N],q[N];
void init(int t)
{
	for(int i=1;i<=2*t;i++)
		fa[i]=i;
}
int getfa(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=getfa(fa[x]);
}
void merg(int x,int y)
{
	fa[getfa(y)]=fa[getfa(x)];
}
bool wow(int x,int y)
{
	return getfa(x)==getfa(y);
}
int main()
{
	cin>>f;
	while(f)
	{
		t=0;
		f--;
		cin>>n;
		unordered_map<int,int>mp;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d",&o[i],&p[i],&q[i]);
			if(!mp.count(o[i]))
			{
				t++;
				mp[o[i]]=t;
			}
			if(!mp.count(p[i]))
			{
				t++;
				mp[p[i]]=t;
			}
		}
		bool c=1;
		init(t);
		for(int i=1;i<=n;i++)
		{
			if(q[i]==1)
			{
				if(wow(mp[o[i]],mp[p[i]]+t))
				{
					cout<<"NO"<<'\n';
					c=0;
					break;
				}
				merg(mp[o[i]],mp[p[i]]);
				merg(mp[o[i]]+t,mp[p[i]]+t);
			}
			else
			{
				if(wow(mp[o[i]],mp[p[i]]))
				{
					cout<<"NO"<<'\n';
					c=0;
					break;
				}
				merg(mp[o[i]],mp[p[i]]+t);
				merg(mp[o[i]]+t,mp[p[i]]);
			}
		}
		if(c)
			cout<<"YES"<<'\n';
	}
	return 0;
}
2022/11/16 13:12
加载中...