ACWING240食物链

• 由于合并之后 X 和 Y 要变成同类，即 X 和 Y 到根节点 py 的距离要相等，因此 px 到 py 的距离要更新为 d[y] - d[x] 。

• d[x] 中存储的是这个点到根节点的距离。这是并查集的拓展用法。因为每次要进行路径压缩，所以在 find 函数里面每次路径压缩的时候便将d[x]更新为 自己到父节点的距离加上父节点到根节点的距离 ，然后 将自己的父节点设为根节点，距离更新为自己到根节点的距离。

• 如果某一动物的排序在另一动物后面，则说明他可以吃掉这种动物。转换为代码便是 (d[x] - d[y] - 1) % 3 == 0 。可以通过这样来判断是否为真话。那么合并的时候也依照这个公式， fx 到 fy 的距离应该更新为 d[y] - d[x] + 1 。这样 fx到fy距离 + d[x] == d[y] 。更新成功。这是一道并查集的应用题，比裸题稍微多了一点要求，是一道很好的练手题。

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 50010;

int n, m, res;
int father[N], d[N];

int find(int x)
{
    if (x != father[x])
    {
        int t = find(father[x]);
        d[x] += d[father[x]];
        father[x] = t;
    }
    return father[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) father[i] = i;
    for (int i = 0; i < m; i ++ )
    {
        int a, x, y;
        cin >> a >> x >> y;
        if (x > n || y > n) res ++ ;
        else
        {
            int fx = find(x), fy = find(y);
            if (a == 1)
            {
                // 如果父亲相同说明出现过，而%3不等于0说明不是同类，是假话 
                if (fx == fy && (d[x] - d[y]) % 3) res ++ ; 
                else if (fx != fy)
                {
                    father[fx] = fy;
                    d[fx] = d[y] - d[x]; // 将fx到fy的距离更新为d[y] - d[x] 
                }
            }
            else if (a == 2)
            {
                if (fx == fy && (d[x] - d[y] - 1) % 3) res ++ ;
                else if (fx != fy)
                {
                    father[fx] = fy;
                    d[fx] = d[y] + 1 - d[x];
                }
            }
        }   
    }
    cout << res << endl;
    return 0;
}