题目来源： 原创

基准时间限制：1 秒 空间限制：131072 KB 分值: 160 

 收藏

 关注

给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示例

31 2 11 3 12 3 0

Output示例

YESYESNO

考虑用并查集维护相等关系，用set维护不等关系。

就是说相等的放在一个并查集里面，这个集合开个set，其中存放和它不等的并查集序号。

如果限制不相等，显然就是在set中添加元素

如果限制相等，那么我们可以通过启发式合并将两个并查集以及他们对应的set合并

复杂度为n*(logn)^2

代码：

#include 
    
       #include 
     
        #include 
      
         #include 
       
          #include 
        
           #include 
         
          #include 
          
           #include 
           
          
         
        
       
      
     
    

版权声明：本文为博主原创文章，未经博主允许不得转载。