Description

给定多个 $ x_i  x_j $ 是否相等的条件

判断能否实现给每个 $  x_ i  $赋上合适的值满足条件

Solution

考虑用并查集实现

若两个数相等，则表示它们的祖先相同

给出的条件要先排序，把所有相同的条件放在前面先处理

数的范围很大，并查集数组开不下，需要离散化一下

Code

#pragma GCC optimize(3)#include 
    
     using namespace std;const int N = 1000005;int T, n, f[N], hash[N], tot = 0; struct Node {    int a, b, c;}u[N];int getf(int u) {    return u == f[u] ? u : f[u] = getf(f[u]);}template 
     
      void read(T &t) {    t = 0; T m = 1; char ch = getchar();    while(ch < '0' || ch > '9') { if(ch == '-') m = -1; ch = getchar(); }    while(ch >= '0' && ch <= '9') { t = (t << 3) + (t << 1) + (ch & 15); ch = getchar(); }    t *= m;}bool cmp(const Node &a, const Node &b) {    return a.c > b.c;}int main() {    read(T);    while(T--) {        tot = 0;        memset(f, 0, sizeof(f));        read(n);        bool fl = true;        for(register int i = 1; i <= n; i++) {            read(u[i].a), read(u[i].b), read(u[i].c);            hash[++tot] = u[i].a;            hash[++tot] = u[i].b;        }        sort(hash + 1, hash + tot + 1);        int siz = unique(hash + 1, hash + tot + 1) - hash - 1;        for(register int i = 1; i <= n; i++) {            u[i].a = lower_bound(hash + 1, hash + siz + 1, u[i].a) - hash;            u[i].b = lower_bound(hash + 1, hash + siz + 1, u[i].b) - hash;        }        for(register int i = 1; i <= siz * 2; i++) f[i] = i;        sort(u + 1, u + n + 1, cmp);        for(register int i = 1; i <= n; i++) {            int A = u[i].a, B = u[i].b, C = u[i].c;            int F1 = getf(A), F2 = getf(B);            if(C == 0) {                if(F1 == F2) { fl = false; break; }            } else {                if(F1 != F2) f[F1] = f[F2];            }        }        printf("%s\n", fl ? "YES" : "NO");    }    return 0;}