给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
考虑用并查集维护相等关系，用set维护不等关系。
就是说相等的放在一个并查集里面，这个集合开个set，其中存放和它不等的并查集序号。
如果限制不相等，显然就是在set中添加元素
如果限制相等，那么我们可以通过启发式合并将两个并查集以及他们对应的set合并
复杂度为n*(logn)^2
代码：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#pragma warning(disable:4996)
using namespace std; int pre[200005];
int x[100005];
int y[100005];
int oper[100005];
int num[200005];
set<int> notequal[50005];
int n,m,shizu1,shizu2;
set<int>::iterator it1,it2;
map<int,int>hash_m; int findpre(int x)
{
while(x!=pre[x])
{
x=pre[x];
}
return x;
} void union_set(int x,int y)
{
int pre_x = x;
int pre_y = y; if(pre_x == pre_y)
return;
else if(notequal[pre_y].size()>notequal[pre_x].size())
{
int temp = pre_x;
pre_x = pre_y;
pre_y = temp;
} pre[pre_y]=pre_x; for(it2=notequal[pre_y].begin();it2!=notequal[pre_y].end();it2++)
{
notequal[pre_x].insert(*it2);
}
} template <class F,class T>
F bin_search(F s,F e,T val)
{
F L = s;
F R = e-1; while(L<=R)
{
F mid = L + (R-L)/2;
if(!(*mid<val || val < *mid))
{
return mid;
}
else if(val < *mid)
{
R = mid -1;
}
else
{
L= mid + 1;
}
}
} int main()
{
//freopen("i.txt","r",stdin);
//freopen("o.txt","w",stdout); int i,j,test,num_m,le,re;
num_m=0;
scanf("%d",&test);
for(j=1;j<=test;j++)
{
scanf("%d%d%d",&x[j],&y[j],&oper[j]);
num[num_m]=x[j];
pre[num_m]=num_m;
num_m++; num[num_m]=y[j];
pre[num_m]=num_m;
num_m++;
}
sort(num,num+num_m);
num_m=unique(num,num+num_m)-num;
for(j=0;j<num_m;j++)
{
hash_m[num[j]]=j;
}
for(j=1;j<=test;j++)
{
le=hash_m[x[j]];
re=hash_m[y[j]];
shizu1=findpre(re);
shizu2=findpre(le);
if(oper[j]==1)
{
int flag=0; if(notequal[shizu2].size()<notequal[shizu1].size())
{
it1=notequal[shizu2].find(shizu1);
if(it1!=notequal[shizu2].end()) //找到
{
flag=1;
}
if(flag==0)
{
for(it1=notequal[shizu2].begin();it1!=notequal[shizu2].end();it1++)
{
if(shizu1 == findpre(*it1))
{
flag=1;
break;
}
}
}
}
else
{
it2=notequal[shizu1].find(shizu2);
if(it2!=notequal[shizu1].end()) //找到
{
flag=1;
}
for(it2=notequal[shizu1].begin();it2!=notequal[shizu1].end();it2++)
{
if(shizu2 == findpre(*it2))
{
flag=1;
break;
}
}
} if(flag==0)
{
union_set(shizu1,shizu2);
printf("YES\n");
}
else
{
printf("NO\n");
}
}
else
{
if(shizu1==shizu2)
{
printf("NO\n");
}
else
{
notequal[shizu2].insert(shizu1);
notequal[shizu1].insert(shizu2);
printf("YES\n");
}
}
}
//system("pause");
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。