题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1515
给n组操作，每组操作形式为x y p。
当p为1时，如果第x变量和第y个变量可以相等，则输出YES，并限制他们相等；否则输出NO，并忽略此次操作。
当p为0时，如果第x变量和第y个变量可以不相等，则输出YES，并限制他们不相等 ；否则输出NO，并忽略此次操作。
Input
输入一个数n表示操作的次数(n<=1*10^5)
接下来n行每行三个数x,y,p（x,y<=1*10^8,p=0 or 1）
Output
对于n行操作，分别输出n行YES或者NO
Input示例
3
1 2 1
1 3 1
2 3 0
Output示例
YES
YES
NO
题解：
1.一开始还以为跟这题POJ2492 A Bug's Life一样，直接种类并查集即可，结果连测试数据都过不了。后来发现：当A!=B， B!=C时，A可能等于C，也可能不等于C，而对于POJ2492，因为元素只有两种，所以A肯定等于C。自己就是受这一题的影响，一直认为A肯定等于C，思想僵化……
2.所以，同一个集合里的元素只能是相等的，即不能用种类并查集了。对此的解决策略是：为每个集合添加一个与之不相等集合的队列。
3.当规定两个集合不相等时，只需各自把对方加入到自己的“不相等”队列即可；当规定两集合相等时，即需要合并两集合，此时，就需要用到启发式合并了：把“不相等”队列小的合并到“不相等”队列大的集合上。
4.启发式合并的时间复杂度为：O(nlogn)，证明：每一次把小集合合并到大集合上，则新集合的大小至少为小集合的两倍，即表明每合并一次，集合的大小可翻倍，由于只有n个元素，那么最多只能有logn次翻倍；每一次翻倍，最多只能有n个元素参与，所以时间复杂度为O(nlogn)。
5.在检验两集合是否不相等时，由于还用到了find()函数，所以总体的时间复杂度为：O(n*logn*logn)
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = 2e5+; int fa[MAXN];
map<int,int>M; //用于离散化
vector<int>s[MAXN]; //记录与这个变量不相等的变量
int find(int x)
{
return fa[x]==-?x:fa[x]=find(fa[x]);
} bool Union(int u, int v, int w)
{
u = find(u);
v = find(v); if(u==v) //如果在同一个集合，即两变量相等，则直接判断
return (w==);
else //不在同一个集合
{
if(s[u].size()>s[v].size()) swap(u,v);
bool flag = false; //判断两变量是否不相等
int sz = s[u].size();
for(int i = ; i<sz; i++) //用小的集合去判断
{
flag |= find(s[u][i])==v; //s[u][i]可能已经被合并到某个集合，所以要找到其当前所在的集合
if(flag) break; //加上这个判断，不然被卡常数
} if(flag) //不过两变量不相等，则直接判断，并返回
return (w==);
else if(w==) //否则，如果要求两变量相等，则两者所在的集合
{
fa[u] = v;
sz = s[u].size();
for(int i = ; i<sz; i++) //启发式合并的关键
s[v].push_back(s[u][i]);
s[u].clear();
}
else //如果要求两变量不相等，则各自把对方加入到自己的“不相等”队列
{
s[u].push_back(v);
s[v].push_back(u);
}
}
return true;
} int main()
{
int n, m;
while(scanf("%d",&n)!=EOF)
{
M.clear();
m = ;
memset(fa,-,sizeof(fa));
for(int i = ; i<MAXN; i++)
s[i].clear();
for(int i = ; i<=n; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
if(M.find(u)==M.end()) M[u] = ++m;
if(M.find(v)==M.end()) M[v] = ++m; if(Union(M[u],M[v],!w)) puts("YES");
else puts("NO");
}
}
}