算法竞赛进阶指南，194页，并查集
本题要点：
1、离散化，等式中的数字 10^9， 而一共 2 * 10^5 个不同的数字， 把所有数字装在数组a，然后排序，去重，
放到数组b， 原来的一个数字映射到数组b的一个下标。 用 lower_bound 来查找每一个数字对应的下标。
2、 并查集，相等关系具有传递性，扫描所有的式子，如果是等式（a == b），将 a 和 b 所在的并查集合并；
然后扫描所有的不等式 （a != b），看看 a 和 b 是否属于同一个并查集即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 100010;
int n, T, tot, m;
int fa[MaxN];
int a[MaxN * 2], b[MaxN * 2];struct Equ
{
int a, b;int flag;
}e[MaxN];int get(int x)
{
if(x == fa[x]){
return x;}return fa[x] = get(fa[x]);
} void merge(int x, int y)
{
fa[get(x)] = get(y);
}void solve()
{
m = 0;sort(a + 1, a + tot + 1);for(int i = 1; i <= tot; ++i){
if(1 == i || a[i] != a[i - 1]){
b[++m] = a[i]; }}for(int i = 1; i <= m; ++i){
fa[i] = i;}int x, y;for(int i = 1; i <= n; ++i){
if(1 == e[i].flag){
x = lower_bound(b + 1, b + m + 1, e[i].a) - b;y = lower_bound(b + 1, b + m + 1, e[i].b) - b;merge(x, y); }}for(int i = 1; i <= n; ++i){
if(0 == e[i].flag) {
x = lower_bound(b + 1, b + m + 1, e[i].a) - b;y = lower_bound(b + 1, b + m + 1, e[i].b) - b;if(get(x) == get(y)){
printf("NO\n");return;}}}printf("YES\n");
}int main()
{
scanf("%d", &T);while(T--){
tot = 0;scanf("%d", &n); for(int i = 1; i <= n; ++i){
scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].flag); a[++tot] = e[i].a, a[++tot] = e[i].b;}solve();}return 0;
}/* 2 2 1 2 1 1 2 0 2 1 2 1 2 1 1 *//* NO YES *//* 2 3 1 2 1 2 3 1 3 1 1 4 1 2 1 2 3 1 3 4 1 1 4 0 *//* YES NO */