0
已解决
赵逸凡
初级启示者
初级启示者
一道看起来很简单的题目,但不知道怎么错了。
#include<iostream>
#include<queue>
using namespace std;
long long n,m,fa[1000010<<1],f,t;
struct node{
long long a1,x1,y1;
bool operator<(const node& tmp)const{
return a1<tmp.a1;
}
};
priority_queue<node> q;
void init()
{
for(long long i=1;i<=n;i++)
fa[i]=i;
}
long long find(long long x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
void unite(long long x,long long y)
{
x=find(x);
y=find(y);
fa[x]=y;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
init();
for(long long i=1;i<=n;i++)
{
long long x,y,a;
cin>>x>>y>>a;
q.push((node){a,x,y});
}
while(!q.empty())
{
node h=q.top();
q.pop();
long long a=h.a1;
long long x=h.x1;
long long y=h.y1;
if(a==1)
unite(x,y);
if(a==0)
{
x=find(x);
y=find(y);
if(x==y)
f=1;
}
}
if(f==1)
cout<<"NO\n";
if(f==0)
cout<<"YES\n";
f=0;
}
return 0;
}
评测结果:
我的思路就是用堆来将相等关系式放在前面,不等关系式放在后面,再用并查集判断矛盾,然而为什么WA 4个点?