30pts,RE#2,其他WA求调
查看原帖
30pts,RE#2,其他WA求调
684866
wangborui123楼主2025/7/30 00:02
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n;
unordered_map<int,int>mp;
struct MP{
	int fa[N],sfa[N];
	void init()
	{
		for(int i=0;i<N;i++)
		{
			fa[i]=i;sfa[i]=1;
		}
		return;
	}
	int find(int i)
	{
		if(fa[i]==i)return i;
		return (fa[i]=find(fa[i]));
	}
	void merge(int i,int j)
	{
		i=find(i),j=find(j);
		if(sfa[i]>sfa[j])swap(i,j);
		fa[i]=fa[j];
		sfa[j]+=sfa[i];
		return;
	}
}st;
struct ask
{
	int x,y,e;
}a[N];
bool cmp(ask x1,ask x2){return x1.e>x2.e;}
void solve()
{
	st.init();mp.clear();
	int cnt=1;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].e;
		if(!mp.count(a[i].x))
		{
			mp[a[i].x]=cnt;cnt++;
		}
		if(!mp.count(a[i].y))
		{
			mp[a[i].y]=cnt;cnt++;
		}
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		if(a[i].e==1)
		{
			st.merge(mp[a[i].x],mp[a[i].y]);
		}
		else
		{
			if(st.find(a[i].x)==st.find(a[i].y))
			{
				cout<<"NO\n";
				return;
			}
		}
	}
	cout<<"YES\n";
	return;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	int _;cin>>_;
	while(_--)
	{
		cin>>n;
		solve();
	}
	return 0;
}

2025/7/30 00:02
加载中...