并查集+ 离散化
首先本题的数据范围很大,需要离散化,
STL离散化代码:
//dat是原数据,id是编号,sub是数据的副本
sort(sub + 1, sub + tot + 1);
size = unique(sub + 1, sub + tot + 1) - sub - 1;
for(int i = 1; i <= tot; i++) {
id[i] = lower_bound(sub + 1, sub + size + 1, dat[i]) - sub;
}
并查集所能维护的是具有传递性的关系,比如本题中 等于 就是这样的关系,而不等就不是.
所以本题的思路非常简单,首先处理出来等于的关系,对于每一个不等的关系找矛盾即可
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN = 100005;
int init() {
int rv = 0, fh = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') fh = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
rv = (rv<<1) + (rv<<3) + c - '0';
c = getchar();
}
return fh *rv;
}
struct opt{
int x, y;
bool f;
}e[MAXN];
int T, n, id[MAXN<<1], dat[MAXN<<1], tot, sub[MAXN<<1], size, fa[MAXN<<2];
int find(int x) {
if(fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
void merge(int x, int y) {
if(x == y) return;
int r1 = find(x), r2 = find(y);
if(r1 != r2) fa[r1] = r2;
}
int main() {
T = init();
while(T--){
memset(e, 0, sizeof(e));
n = init();
tot = 0; size = 0;
for(int i = 1; i <= n; i++) {
e[i].x = init(); e[i].y = init(); e[i].f = init();
tot++; dat[tot] = sub[tot] = e[i].x;
tot++; dat[tot] = sub[tot] = e[i].y;
}
sort(sub + 1, sub + tot + 1);
size = unique(sub + 1, sub + tot + 1) - sub - 1;
for(int i = 1; i <= tot; i++) {
id[i] = lower_bound(sub + 1, sub + size + 1, dat[i]) - sub;
}
for(int i = 1; i <= size; i++) {
fa[i] = i;
}
/*for(int i = 1; i <= tot ; i++) printf("%d %d\n", id[i], dat[i]);
printf("\n");*/
bool fff = 0;
for(int i = 1; i <= n; i++) {
e[i].x = id[i * 2 - 1]; e[i].y = id[i * 2];
if(e[i].f) {
merge(e[i].x, e[i].y);
}
}
for(int i = 1; i <= n; i++) {
if(!e[i].f) {
if(find(e[i].x) == find(e[i].y)) {fff = 1;break;}
}
}
if(!fff) {
printf("YES\n");
}else printf("NO\n");
}
return 0;
}