来自FallDream 的博客，未经允许，请勿转载，谢谢。
在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本：假设x1,x2,x3,…代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2，x2=x3，x3=x4，x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
现在给出一些约束满足问题，请分别对它们进行判定.
t<=10 n<=10^5
noi2015的签到题吧？
把相同的并查集搞起来，不同的查一查就行了。
#include<iostream> #include<cstdio> #include<map> #define pa pair<int,int> #define mp(x,y) make_pair(x,y) #define MN 1000000 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int s[MN*2+5],n,top=0,cnt=0; map<int,int> mp; pa q[MN+5]; inline int getfa(int x){return s[x]==x?x:s[x]=getfa(s[x]);} void Union(int x,int y){int f1=getfa(x),f2=getfa(y);if(f1!=f2)s[f1]=f2;} int main() { for(int t=read();t;--t) { n=read();mp.clear();cnt=top=0; for(int i=1;i<=n;++i) { int x=read(),y=read(),e=read(); !mp[x]?(mp[x]=++cnt,s[cnt]=cnt):0; !mp[y]?(mp[y]=++cnt,s[cnt]=cnt):0; if(e) Union(mp[x],mp[y]); else q[++top]=mp(mp[x],mp[y]); } bool flag=true; for(int i=1;i<=top&&flag;++i) if(getfa(q[i].first)==getfa(q[i].second)) puts("NO"),flag=false; if(flag) puts("YES"); } return 0; }