AcWing 237. 程序自动分析
原题链接
中等
作者:
修仙修仙
,
2024-02-05 18:33:15
,
所有人可见
,
阅读 24
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
int n;
struct node
{
int x,y;
};
int find(unordered_map<int,int>&p,int x)
{
if(p[x]!=x) p[x]=find(p,p[x]);
return p[x];
}
int main()
{ ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{ unordered_map<int,int>p;
unordered_map<int,bool>mp;
vector<node>q;
cin>>n;
bool f=0;
for (int i=1;i<=n;i++)
{
int x,y,z;
cin>>x>>y>>z;
// cout<<x<<" "<<y<<" "<<z<<endl;
if(!mp[x])
{
mp[x]=1;
p[x]=x;
}
if(!mp[y])
{
mp[y]=1;
p[y]=y;
}
int a=find(p,x);
int b=find(p,y);
//cout<<a<<" "<<b<<endl;
if(z==1) {if(a!=b)p[a]=b;}
else
{
if(a==b)
{
f=1;
}
else q.push_back({a,b});
}
//cout<<"f=="<<f<<endl;
}
if(f) cout<<"NO\n";
else
{
for(auto z:q)
{
int a=find(p,z.x);
int b=find(p,z.y);
if(a==b) {
f=1;
break;
}
}
if(f)cout<<"NO\n";
else cout<<"YES\n";
}
}
}