「Bzoj 4195」「Noi2015」程序自动分析 (并查集)

BZOJ 4195
题意：给出$n$组关系，$x_i=x_j$或$x_i≠x_j$，请判断是否能有一种方法满足情况。

想到图论就不难了……
显然将等于看作无向边，然后一个联通块的都是相等的。
然后再枚举每个不等的二元组，判是否在一个联通块即可。
用并查集维护。

注意要离散化。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 1000000 + 5;

    struct data {int x, y, e;} opt[MAXN];
    int q, whw[MAXN * 2], gg, f[MAXN * 2];

    int getRealID(int x) {return lower_bound(whw + 1, whw + 1 + gg, x) - whw;}
    int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}

    void clean() {
        gg = 0;
    }
    int solve() {
        clean();
        scanf("%d", &q);
        for (int i = 1; i <= q; ++i) scanf("%d%d%d", &opt[i].x, &opt[i].y, &opt[i].e), whw[++gg] = opt[i].x, whw[++gg] = opt[i].y;
        sort(whw + 1, whw + 1 + gg), gg = unique(whw + 1, whw + 1 + gg) - whw - 1;
        for (int i = 1; i <= gg; ++i) f[i] = i;
        for (int i = 1; i <= q; ++i) if (opt[i].e == 1) {
            int x = find(getRealID(opt[i].x)), y = find(getRealID(opt[i].y));
            if (x != y) f[x] = y;
        }
        for (int i = 1; i <= gg; ++i) find(i);
        for (int i = 1; i <= q; ++i) if (opt[i].e == 0) {
            int x = find(getRealID(opt[i].x)), y = find(getRealID(opt[i].y));
            if (x == y) return printf("NO\n"), 0;
        }
        return printf("YES\n"), 0;
        return 0;
    }
}
int main() {
    int t; cin >> t;
    while (t--) flyinthesky::solve();
    return 0;
}