题目描述

给定 $n$ 个等式或不等式（$\neq$），判断这 $n$ 个式子是否存在。

思路

考虑转化。

若 $x_1=x_2=\dots=x_k$，称为一个等式组，那么就等价于这 $k$ 个数等于一个共同的数值，那么可以看作他们共同的祖先。

那么对于所以不同的等式组，都把他们指向一个共同的祖先。

所以用并查集进行维护。

再处理不等式。对于任意一个不等式，能被满足当且仅当这两个指向的祖先不同。

注意

• $x$ 的值域是 $[1,10^9]$，祖先数组不能开这么大的空间，故需要离散化。

• 要先处理完等式组，再处理不等式。

离散化模板（$num$ 是输入的数的集合，用 vector 储存）：

sort(num.begin(), num.end());
num.erase(unique(num.begin(), num.end()), num.end());

那么对于一个数，它离散化后的数就是（lower_bound() 是寻找一个大于等于该数的下标）：

x = lower_bound(num.begin(), num.end(), x) - num.begin();

时间复杂度 $O(n\log n)$。

代码

#include<bits/stdc++.h>

#define ll long long
#define y1 caibictq
#define P pair<int, int>
#define fi first
#define se second

using namespace std;

const int MAXN = 200010;
const int MAXM = 100010;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int n, m, k;
int tot, cnt, ans;

int read() {
    int f = 1, s = 0;
    char ch = getchar();
    while ('0' > ch || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while ('0' <= ch && ch <= '9') {s = (s << 1) + (s << 3) + ((int)ch ^ 48); ch = getchar();}
    return s * f;
}

int a[MAXN], f[MAXN];

int find(int x) {
    while (x != f[x]) x = f[x] = f[f[x]];
    return x;
}

struct data {
    int a, b, e;    
}x[MAXN];

bool cmp(data x, data y) {
    return x.e > y.e;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        vector<int> num;
        num.push_back(0);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d%d", &x[i].a, &x[i].b, &x[i].e);
            num.push_back(x[i].a);
            num.push_back(x[i].b);
        }
        sort(num.begin(), num.end());
        num.erase(unique(num.begin(), num.end()), num.end());
        for (int i = 1; i < num.size(); i++) {
            f[i] = i;
        }
        int ok = 1;
        for (int i = 1; i <= n; i++) {
            x[i].a = lower_bound(num.begin(), num.end(), x[i].a) - num.begin();
            x[i].b = lower_bound(num.begin(), num.end(), x[i].b) - num.begin();
        }
        sort(x + 1, x + n + 1, cmp);
        for (int i = 1; i <= n; i++) {
            if (x[i].e) f[find(x[i].a)] = find(x[i].b);
            else if (find(x[i].a) == find(x[i].b)) {
                ok = 0; break;
            }
        }

        if (ok) puts("YES");
        else puts("NO");
    }
    return 0;
}