食物链 - POJ1182

题意:A国有3个物种,A捕食B,B捕食C,C捕食A.某人对A国的n个动物发表评价,内容如下:
1 x y : x和y是一个物种
2 x y : x捕食y
如果这个人的某个评论与前文的真话出现矛盾或x,y>n,这个评论成为假话,反之成为真话.
求他说了多少假话.


分析:由于捕食关系成环,如果我们发现了一条食物链A->B->C->D->E->F...,那么一定有A=D,B=E,C=F,以此类推.也就是说食物链上每3个动物都是不同的,隔着两个的动物是相同的.(显然),因此我们可以记录每只动物距所在食物链最前端的距离.这个就可以使用并查集完成.
如果我们发现了这样的两条食物链:
A->B
D->E
且某人说B和E是同一个物种,按照定义,这是句真话.因此我们需要将两个食物链合并.
合并连边A->D,为了保证B和E仍然是一个物种,D距离A的距离应该设为0.保证了食物链的合法性.

补充:网络上普遍的做法是保存节点与父节点的吃与被吃的关系,但这种关系不好想,也不容易推广到物种更多的食物链上去.这篇博客的做法,我自认为是基于同余的easy but effective的做法.