【题目】

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本：假设 𝑥1, 𝑥2, 𝑥3, ⋯ 代表程序中出现的变量，给定 𝑛 个形如 𝑥𝑖 = 𝑥𝑗 或 𝑥𝑖 ≠ 𝑥𝑗 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为： 𝑥1 = 𝑥2, 𝑥2 = 𝑥3, 𝑥3 = 𝑥4, 𝑥1 ≠ 𝑥4 ，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
现在给出一些约束满足问题，请分别对它们进行判定。

【题意】

输入两个建立关系的对象x,y，然后输入一个建立关系的命令。如果为1就是建立x相等y的关系，如果为0则是建立x不相等y的关系。当前建立的关系不能于之前的关系产生矛盾。如果产生矛盾则输出"NO"，否则直到最后都没产生矛盾则输出"YES"。

【题解】

看完题目，可以知道也许能用并查集做，再看数据范围，可以知道不能单纯的使用并查集，还需要进行离散化。离散化的方法有两种，一种是使用单纯的数组进行离散化，还有就是使用封装好的map。前者时间复杂度相对会低一些，后者则是使用难度、代码量和出错几率会相对低一些。因为题目给的时间很宽裕，所以果断采取map来进行离散化。离散并且按命令1和命令0对x,y进行分组存储，输入数据并存储完后，先对1的命令进行并查集合并，最后则是对命令0的x,y枚举判断是否是属于同一个集合内，如果被判定为相同，则代表本来相等的对象，被再次要求不相等，这就产生了矛盾，直接输出"NO"即可，如果到最后都没有产生矛盾，则输出"YES"。

离散化：既对数字偏大，但总数偏小的数据进行重新编号存储，并应用在程序之中。

时间复杂度：并查集的操作时间复杂度是会比的速度要快,红黑树的map时间复杂度为,整体复杂度大致为。

代码:

#include<iostream>
#include<cstring>
#include<sstream>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<list>
#include<set>
#include<map>
#include<algorithm>
#define fi first
#define se second
#define MP make_pair
#define P pair<int,int>
#define PLL pair<ll,ll>
#define lc (p<<1)
#define rc (p<<1|1)
#define MID (tree[p].l+tree[p].r)>>1
#define Sca(x) scanf("%d",&x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)
#define Scl2(x,y) scanf("%lld%lld",&x,&y)
#define Scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define Pri(x) printf("%d\n",x)
#define Prl(x) printf("%lld\n",x)
#define For(i,x,y) for(int i=x;i<=y;i++)
#define _For(i,x,y) for(int i=x;i>=y;i--)
#define FAST_IO std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define STOP system("pause")
#define ll long long
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
const double Pi = acos(-1.0);
using namespace std;
template <class T>void tomax(T&a,T b){ a=max(a,b); }  
template <class T>void tomin(T&a,T b){ a=min(a,b); }
const int N=1e6+5;
map<int,int> num;
int uck[N<<1],n,id=0,id0=0,id1=0;
struct Node{
    int x,y;
}may0[N],may1[N];
int find(int x){
    i***[x]==x) return x;
    return uck[x]=find(uck[x]);
}
inline void merge(int x,int y){
    int t1(find(x)),t2(find(y));
    if(t1!=t2) uck[t2]=t1;
}
inline void init(int n){
    For(i,1,n) uck[i]=i;
    num.clear();
}
int main(){
    int T; Sca(T);
    while(T--){
        Sca(n);
        id=0; id0=0; id1=0;
        bool flag=1;
        For(i,1,n){
            int x,y,cmd;
            Sca3(x,y,cmd);
            if(num[x]==0) num[x]=++id;
            if(num[y]==0) num[y]=++id;

            if(cmd==1) may1[++id1]=Node{num[x],num[y]};
            else may0[++id0]=Node{num[x],num[y]};
        }
        init(id);
        For(i,1,id1){
            int x=may1[i].x,y=may1[i].y;
            merge(x,y);
        }
        For(i,1,id0){
            int x=may0[i].x,y=may0[i].y;
            if(find(x)==find(y)){
                flag=0;
                break;
            }
        }
        if(flag) puts("YES");
        else puts("NO");
    }
}