POJ 2492 A Bug's Life 并查集应用

题目大意是给出m个虫子的交配组合，确定其中是否存在同性交配现象。

并查集的常规应用是判断两个元素是否处于同一个集合，但这题如果按照这种常规思路构建模型显然是行不通的。于是在常规的模型基础上增加一个数组sex[a]表示节点a与其根节点（注意和父节点相区分）的性别情况，true表示相同，false表示不同。

如果输入的a、b为同一集合中的元素，则直接比较其与根节点的性别情况即可判断是否为同性。如果处于不同集合，则合并两个集合后再进行比较。但合并之后要重新确定被合并的集合的原根节点与现根节点的性别情况。假设a的根节点为c，b的根节点为d，将d合并到c中，那么d相对于c的性别情况有以下可能：

1. sex[a] == true，sex[b] == true，即a、c的性别相同，b、d的性别相同，可知d，c的性别相反，即sex[d] = false；
2. sex[a] == true，sex[b] == false，即a、c的性别相同，b、d的性别不同，可知d，c的性别相同，即sex[d] = true；
3. sex[a] == false，sex[b] == true，和第二种情况相同，sex[d] = true；
4. sex[a] == false，sex[b] == false，即a、c的性别相反，c、d的性别相反，可知d，c的性别相反，即sex[d] = false；

即sex[d] = sex[a] ^ sex[b];

对sex的更新可以在求根节点的同时进行，根据与父节点的性别关系进行处理即可，利用递归实现非常便捷。此外在合并完成之后需要对被合并的集合内的节点的性别关系进行更新，之后再进行同性判断。

7781952    IwfWcf    2492    Accepted    404K    860MS    G++    1315B    2010-10-23 23:55:30