[51NOD1515] 明辨是非

题目

题目链接 51nod 1515. 题目大意为给你 n 组关系,告知 a_{x_i}a_{x_j} 相等或者不相等,问是否有矛盾,实时询问。
 

思路

注意,普通的关系并查集并不能做,因为不等号不具有传递性。所以,我用并查集维护等于的关系,再用 set 维护每集合与其他集合不等的关系。因为合并 set 是 O(n) 的,所以要启发式合并,即小的合并到大的。
 

代码

 

完结

发表评论

电子邮件地址不会被公开。 必填项已用*标注