训练3　食物链

题目描述（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，则为假话。