题目描述（POJ1182）： 在动物王国中有三类动物A、B、C，这三类动物的食物链构成了有趣的环形：A吃B，B吃C，C吃A。现有 N 个动物，编号为1～ N 。每个动物都是A、B、C中的一种。食物链关系有两种描述：1 X Y ，表示 X 、 Y 是同类；2 X Y ，表示 X 吃 Y 。对 N 个动物，用上述两种描述方式说出 K 句话，这 K 句话有的是真的，有的是假的。一句话满足以下三个条件之一时，就是假话，否则是真话：①当前的话与前面的某些真话冲突；②在当前的话中 X 或 Y 比 N 大；③当前的话表示 X 吃 X 。请确定假话的数量。

输入： 第1行包含两个整数 N （1≤ N ≤50,000）和 K （0≤ K ≤100,000）。在以下 K 行中，每行都包含三个正整数 C 、 X 、 Y ，其中 C 表示食物链关系描述的种类， C =1或2。

输出： 单行输出假话的数量。

题解： 可以使用并查集来查询和合并食物链中动物间的关系。fa[ i ]表示第 i 个动物的集合号； d [ i ]表示第 i 个动物在食物链中的深度；在 c x y 中， c 表示食物链关系的种类， c =1表示 x、y 是同类， c =2表示 x 吃 y 。并查集的基本操作是相同的，因为本题用深度来表达动物在食物链中的关系，所以需要考虑3个问题：查找时如何更新深度？合并时如何更新深度？深度满足什么关系是真话？下面分别进行解答。

（1）查找时如何更新深度。首先找祖宗，集合号等于自身时回归，在回归过程中需要更新集合号为祖宗的集合号，更新当前节点的深度累加其父节点的深度。但是本题只有三种类型的动物，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。也就是说，深度只可以是0、1、2，因此若深度等于3，则将深度转换为0（模3运算）。当前节点的深度累加其父节点的深度模3运算，即 d [ x ]=( d [ x ]+ d [fx])%3。当输入1吃2、2吃3、3吃4时，并查集如下图中左图所示。当查询1的集合号时，首先找到祖宗4，回归时更新3号节点的深度为1，集合号为4；更新2号节点的深度为2，集合号为4；更新1号节点的深度为0，集合号为4，如下图中右图所示。

（2）合并时如何更新深度。假设 x 的集合号为 a ， y 的集合号为 b ，若 a ≠ b ，则合并集合号fa[ a ]= b ，更新 a 的深度 d [ a ]=( d [ y ]- d [ x ]+3+ c -1)%3。因为该食物链为环形，所以需要取模运算，为避免减法出现负值，进行减法运算后加上3然后取模运算即可。输入6吃2，两个节点属于不同的集合7、4，执行合并，fa[7]=4。更新7的深度为 d [7]=( d [2]- d [6]+3+2-1)%3=2。合并更新后如下图所示。

当下次查询6的集合号时，找到祖宗4，回归时更新6的深度为 d [6]=( d [6]+ d [7])%3=0，查询更新后如下图所示。同1、2号节点的关系表达一致，深度 d =0的节点吃 d =2的节点。

（3）深度满足什么关系是真话。同一集合中的两个节点 x、y 若是同类，则深度差为0；若是 x 吃 y ，则深度差 d [ x ]- d [ y ]=1或者 d [ x ]- d [ y ]=-2。如上图所示，1吃2，高度差为-2；2吃3，高度差为1；3吃1，高度差为1。当高度差为-2时，令其加3，转换为1。当高差为1时，加3变成了4，为了统一，将结果模3即可，若 x 吃 y ，则( d [ x ]- d [ y ]+3)%3=1。在 c x y 指令中， c =1表示 x、y 是同类， c =2表示 x 吃 y 。令 c -1，同类时 c -1=0， x 吃 y 时 c- 1=1，因此无论是同类还是吃的关系，公式统一为( d [ x ]- d [ y ]+3)%3= c -1。若不满足此关系，则为假话。

1. 算法设计

（1）若 x 或 y 大于 n ，或者 x 吃 y （ x = y ），则为假话。

（2）执行 c x y 指令时，首先查询 x 、 y 的集合号。查询集合号回归时，更新路径上每个节点的深度， d [ x ]=( d [ x ]+ d [fx])%3。若 x 的集合号为 a ， y 的集合号为 b ，则分以下两种情况。

· a ≠ b ：合并集合号fa[ a ]= b ，更新 a 的深度 d [ a ]=( d [ y ]- d [ x ]+3+ c -1)%3。

· a = b ：若( d [ x ]- d [ y ]+3)%3!= c -1，则为假话。

2. 完美图解

（1）合并。2 1 2：1吃2。首先找到1和2所在的集合号1、2，两个集合号不等，将1的集合号修改为2，更新 d [1]=( d [2]- d [1]+3+2-1)%3=1。

（2）合并。2 2 3：2吃3。首先找到2和3所在的集合号2、3，两个集合号不等，将2的集合号修改为3，更新 d [2]=( d [3]- d [2]+2-1+3)%3=1。

（3）查询。1 1 3：查询1和3是同类。首先查询1的集合号，在查询过程中，1的父节点为2，2的父节点为3，3的父节点为3，更新1的集合号等于父节点的集合号3，将当前节点的 d 值加上其父节点的 d 值， d [1]+= d [2]=2。回归时集合号统一为3，1的集合号和3的集合号相等，但它们是不是同类呢？若满足( d [ x ]- d [ y ]+3)%3=0，则是同类，否则不是同类。也就是说，当集合号相等时，若 x 、 y 为同类，则它们的 d 值之差加3模3后为0。此时( d [1]- d [3]+3)%3=2，因此为假话。

（4）合并。2 3 1：3吃1。首先找到3和1所在的集合祖宗3、3，两个集合号相等，若满足( d [ x ]- d [ y ]+3)%3=1，就是真话，也就是说，当集合号相等时，若 x 吃 y ，则它们的 d 值之差加3模3后为1。此时( d [3]- d [1]+3)%3=1，是真话。

（5）查询。1 5 5：查询5和5是否是同类。首先查询到5和5的集合号均为5，集合号相等，若满足( d [ x ]- d [ y ]+3)%3=0，则是同类，否则不是同类。此时( d [5]- d [5]+3)%3=0，是真话。

（6）合并。2 5 2：5吃2。首先找到5和2所在的集合祖宗5、3，两个集合号不等，将5的集合号修改为3，更新 d [5]=( d [2]- d [5]+2-1+3)%3=2。

（7）合并。2 6 1：6吃1。首先找到6和1所在的集合祖宗6、3，两个集合号不等，将6的集合号修改为3，更新 d [6]=( d [1]- d [6]+2-1+3)%3=0。

（8）合并。2 3 7：3吃7。首先找到3和7所在的集合祖宗3、7，两个集合号不等，将3的集合号修改为7，更新 d [3]=( d [7]- d [3]+2-1+3)%3=1，如下图中左图所示。下次查询6时，会更新从6到祖宗7的所有节点的集合号和 d 值，如下图中右图所示。

3. 算法实现

（1）初始化。

（2）查找集合号。查询 x 、 y 的集合号，在返回过程中，除了统一集合号，还需要更新 d 值（将当前节点的 d 值累加其父节点的 d 值模3）。

（3）判断假话数量。对输入的每条指令，若 x 或 y 大于 n ，或 x 吃 y （ x = y ），则为假话，计数器加1；否则查询集合号，若 x 的集合号为 a ， y 的集合号为 b ，则 a ≠ b 时合并集合号fa[ a ]= b ，更新 a 的深度 d [ a ]=( d [ y ]- d [ x ]+3+ c -1)%3；在 a = b 时进行判断，若( d [ x ]- d [ y ]+3)%3!= c -1，则为假话。 gxbnxq1Pz6rYFCIqgvgvwsre7aXvVmGaZJzjKnzshGP7lsjTN/mp1afD2yk58H5a