AcWing 237. 程序自动分析 “NOI最简单的一道题”
原题链接
中等
作者:
ye_che
,
2021-06-24 20:09:46
,
所有人可见
,
阅读 664
#include<bits/stdc++.h>
using namespace std;
int n, t, cnt, a[100100], b[100100], c[100100], p[200100];
unordered_map<int, int> mp;
int getp(int x)
{
if(mp.count(x) == 0) mp[x] = ++cnt;
return mp[x];
}
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void mer(int a, int b)
{
int pa = find(getp(a)), pb = find(getp(b));
if(pa != pb) p[pa] = pb;
}
int main()
{
cin >> t;
while(t --)
{
cin >> n;
mp.clear();
cnt = 0;
for(int i = 1; i <= n; i ++) cin >> a[i] >> b[i] >> c[i], getp(a[i]), getp(b[i]);
for(int i = 1; i <= n << 1; i ++) p[i] = i;
for(int i = 1; i <= n; i ++) if(c[i]) mer(a[i], b[i]);
bool flag = true;
for(int i = 1; i <= n; i ++) if(!c[i] && find(getp(a[i])) == find(getp(b[i]))) flag = false;
if(flag) cout << "YES\n"; else cout << "NO\n";
}
}