AcWing 237. 程序自动分析
原题链接
中等
作者:
小.bug
,
2022-05-16 11:37:08
,
所有人可见
,
阅读 142
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int p[N];
unordered_map<int,int> h;
int idx;
struct Query{
int a, b, c;
}q[N];
int n, T;
int x, y, op;
int get(int x)
{
if(!h.count(x)) h[x] = idx ++;
return h[x];
}
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> T;
while(T -- )
{
cin >> n;
idx = 0;
h.clear();
for(int i = 0; i < n; i++)
{
cin >> x >> y >> op;
q[i] = {get(x),get(y),op};
}
for(int i = 0; i < idx; i++) p[i] = i;
for(int i = 0; i < n; i++)
{
if(q[i].c == 1) p[find(q[i].a)] = find(q[i].b);
}
int flag = 1;
for(int i = 0; i < n; i++)
{
if(q[i].c == 0 && find(q[i].a) == find(q[i].b))
{
flag = 0;
break;
}
}
if(flag) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}