AcWing 237. 程序自动分析
原题链接
中等
作者:
郡呈
,
2020-05-25 00:18:53
,
所有人可见
,
阅读 718
/*
1. 对1e9级别不需保序的数据离散化到2e6级别
2. 合并所有相等条件
3. 检查所有非等条件
cin TLE了
需要加速
std::ios:sync_with_stdio(false);
std::cin.tie(0);
然后发现是我find函数写错了hhh
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 2e6+10;
int n, cnt = 0;
int p[N];
unordered_map<int, int> S;
struct query{
int x, y, e;
}query[N];
int get(int x) {
if(S.count(x) == 0) S[x] = ++cnt;
return S[x];
}
int find(int x) {
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main() {
// std::ios::sync_with_stdio(false);
// std::cin.tie(0);
int T;
cin >> T;
while(T--) {
S.clear();
cin >> n;
for(int i = 0; i < n; i++) {
int x, y, e;
cin >> x >> y >> e;
query[i] = {get(x), get(y), e};
}
for(int i = 1; i <= cnt; i++) p[i] = i;
for(int i = 0; i < n; i++) {
if(query[i].e == 1) {
int pa = find(query[i].x), pb = find(query[i].y);
p[pa] = pb;
}
}
bool has_confict = false;
for(int i = 0; i < n; i++) {
if(query[i].e == 0) {
int pa = find(query[i].x), pb = find(query[i].y);
if(pa == pb) {
has_confict = true;
break;
}
}
}
if(has_confict) cout << "NO" << endl;
else cout << "YES" << endl;
}
return 0;
}
是scanf不好用了还是快读不香了?(雾)
是我太弱辽呜呜呜,orz快读涉及知识盲区,学到了给大佬递冰激凌hhh