51nod 1515 明辨是非 (并查集)

给n组操作,每组操作形式为x y p。
当p为1时,如果第x变量和第y个变量可以相等,则输出YES,并限制他们相等;否则输出NO,并忽略此次操作。
当p为0时,如果第x变量和第y个变量可以不相等,则输出YES,并限制他们不相等 ;否则输出NO,并忽略此次操作。

首先我们用并查集维护相等数字的集合,对于不等数字,我们对每个相等集合维护一个set保存于这个集合不等的数字是那些。在合并集合时,尽量让set小的集合作为子树。总的复杂化度是O(nlognlogn)

 

 

LEAVE A COMMENT