[POJ2492]A Bug's Life

题目大意

题目链接。题目大意有点污= =,不过也非常的有趣哈。
就是给你n个虫子的交配记录,问你这些虫子中有没有同性恋= =。
大写的

 

分析

其实我们可以把这个题目看成二分图的判定,不断的向图中加边,如果此图不再满足二分图,那么说明虫子中出现gay。(如何保证写题解的时候不笑)
这个时候我们就可以使用关系型并查集来判定。

 

具体

关系型并查集比普通并查集多了一个数组去维护子节点与其父亲节点的关系。
在这题中我用了 r[n]数组 来表示。
如果 r[n] 的值为0,表示该节点与父亲节点为同性,为1则为异性。
当两个节点在同一个集合时,仅仅表示这两个节点有性别关系的描述,而不是说这两个是同性!具体还需要根据 r[n]数组 来计算出来。具体都可以看代码,可以仔细体会 find(x) 函数为什么那么写。
同时,在合并两棵树的时候,也要注意更新 r[n]数组 。

 

代码

c++

Pascal

 

其他

原来写过Pascal版的,不过理解起来好费劲,这会写了C++版,输出时少了一个分号,结果还Debug半天,老了,不中用了啊T^T。

 

未完结

One thought on “[POJ2492]A Bug's Life

  1. Pingback: 并查集 介绍 | 火药

发表评论

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