食物链并查集

把当前节点到根节点的距离看作类别状态。
构造数组d[],d[i] % 3代表不同的状态
2 被根节点吃
1 吃根节点
0 同类
通过并查集来解决，在查找的优化的时候，由于每个节点都指向了根节点，因此距离模3 就是和根节点的关系。每一对动物之间的关系都能用并查集解决。
1.当关系 == 1，同类的时候，先看是否在集合里，如果在，判断距离模3是否相等，若相等则是真话。否则反之。
如果不在集合里，就合并集合，并且设置新加入节点到根节点的距离， 满足条件 (d[x] + ?) %3 = d[y] %3;
2.当关系 == 2，x 吃 y。如果在集合里，判断距离条件 d[x] %3 = d[y] % 3 + 1,满足真话，否则反之。
如果不在集合里，和并集合，设计距离，(d[x] + ? )%3 = d[y] % 3 + 1

样例

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

算法1

(并查集) $O(log(n))$

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N], d[N];

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

int main()
{
    cin.tie(0);
    int n, k,res= 0;
    cin >> n >> k;
    /*初始化的时候d[]都是0，因为自己和自己是同类，当加入到集合里时候再赋值*/
    for(int i = 1; i <= n; ++i)
    {
        p[i] = i;
    }
    while(k--)
    {
        int c, x, y;cin >> c >> x >> y;
        /*找到根节点*/
        if(x > n || y > n)res++;
        else{


        int px = find(x), py = find(y);
        /*xy是同类*/
        if(c == 1)
        {
            if(px == py)
            {
                if((d[x] - d[y]) % 3)res++;
            }
            else 
            {
                /*合并集合*/
                p[px] = py;
                /*对dpx赋值*/
                d[px] = d[y] - d[x];
            }
        }
        else 
        {
            if(px == py)
            {
                if((d[x] - d[y] - 1) % 3)res++;
            }
            else
            {
                p[px] = py;
                /*此时不能取模，不然只有012这三个距离了，构造距离*/
                d[px] = d[y] - d[x] + 1;
            }
        }
    }
    }
    cout << res << endl;
    return 0;
}