Description
在實現程序自動分析的過程中,常常需要判定一些約束條件是否能被同時滿足。
考慮一個約束滿足問題的簡化版本：假設x1,x2,x3,…代表程序中出現的變量，給定n個形如xi=xj或xi≠xj的變量相等/不等的約束條件，請判定是否可以分別為每一個變量賦予恰當的值，使得上述所有約束條件同時被滿足。例如，一個問題中的約束條件為：x1=x2，x2=x3，x3=x4，x1≠x4，這些約束條件顯然是不可能同時被滿足的，因此這個問題應判定為不可被滿足。
現在給出一些約束滿足問題，請分別對它們進行判定。
Input
輸入文件的第1行包含1個正整數t，表示需要判定的問題個數。注意這些問題之間是相互獨立的。
對于每個問題，包含若干行：
第1行包含1個正整數n，表示該問題中需要被滿足的約束條件個數。
接下來n行，每行包括3個整數i,j,e，描述1個相等/不等的約束條件，相鄰整數之間用單個空格隔開。若e=1，則該約束條件為xi=xj；若e=0，則該約束條件為xi≠xj。
Output
輸出文件包括t行。
輸出文件的第k行輸出一個字符串“YES”或者“NO”（不包含引號，字母全部大寫），“YES”表示輸入中的第k個問題判定為可以被滿足，“NO”表示不可被滿足。
Sample Input
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
Sample Output
NO
YES
HINT
在第一個問題中，約束條件為：x1=x2,x1≠x2。這兩個約束條件互相矛盾，因此不可被同時滿足。
在第二個問題中，約束條件為：x1=x2,x2=x1。這兩個約束條件是等價的，可以被同時滿足。
1≤n≤1000000
1≤i,j≤1000000000
Solution
水題一道
由于等號具有連續性，所以先處理所有相等的限制，用并查集維護哪些是相等的
然后判斷不等號，如果有不等號兩邊在同一并查集內，顯然就不行
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define REP(a,b,c) for(register int a=(b),a##end=(c);a<=a##end;++a)
#define DEP(a,b,c) for(register int a=(b),a##end=(c);a>=a##end;--a)
const int MAXN=400000+10;
int T,n,fa[MAXN],lt;
std::vector<int> V;
std::map<int,int> M;
struct node{int x,y,opt;inline bool operator < (const node &A) const {return opt>A.opt;};
};
node limit[MAXN];
template<typename T> inline void read(T &x)
{T data=0,w=1;char ch=0;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')w=-1,ch=getchar();while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void discretization()
{V.clear();M.clear();REP(i,1,n)V.push_back(limit[i].x),V.push_back(limit[i].y);std::sort(V.begin(),V.end());V.erase(std::unique(V.begin(),V.end()),V.end());REP(i,0,V.size()-1)M[V[i]]=i+1;lt=V.size();REP(i,1,n)limit[i].x=M[limit[i].x],limit[i].y=M[limit[i].y];
}
inline int found(int x)
{if(fa[x]!=x)fa[x]=found(fa[x]);return fa[x];
}
int main()
{read(T);while(T--){read(n);REP(i,1,n){int x,y,opt;read(x);read(y);read(opt);limit[i]=(node){x,y,opt};}discretization();std::sort(limit+1,limit+n+1);REP(i,1,lt)fa[i]=i;int mk=1;REP(i,1,n){int u=limit[i].x,v=limit[i].y;if(limit[i].opt)fa[found(u)]=found(v);else if(found(u)==found(v)){mk=0;break;}}puts(mk?"YES":"NO");}return 0;
}
)