时间复杂度：
查询 O（1）
合并 O（1）

题目描述

食物链

重要思路：用并查集维护，然后d[i]的表示i到父节点的距离（但每次询问都会更新为到根节点的距离）

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 5e4 + 10 ;

int p[N];//并查集所用的数据结构，p[i]表示i数的父节点的指针（下标）（基础数据结构的使用）
int d[N];//将食物链的关系抽象成距离关系,d[i]表示i到其父节点的距离（在并查集的基础上添加距离关系）（建模能力）

int res ; //表示假话数量（置于此处为了方便初始化）

int find(int x)  //1.返回根节点的值（坐标） 
                 //2.路径压缩（减少时间复杂度）(使根节点直接成为x的父节点）
{                //3.更新x到其父节点（根节点）的距离  
    if(p[x] != x)
    {
        int t = find(p[x]); //1.用t记录下当前根节点的值
                            //2.更新x的父节点p[x]到根节点的距离
                            //3.路径压缩（使根节点直接成为p【x】的父节点）
        d[x] += d[p[x]];
        p[x] = t ;
    }
    return p[x];
}

int main()
{
    int n , m ;
    cin >> n >> m ; //输入
    //
    for(int i = 1 ; i <= n ; i ++ ) p[i] = i ; // 初始化，每个节点都是一座孤岛
    for(int i = 1 ; i <= n ; i ++ ) d[i] = 0 ; //每个节点到其父节点（自身）距离为0
    // 自己与自己必然是同一类（其实已经初始化）

    while( m -- )   // 处理m组输入
    {
        int l , x , y ;// l代表当前判断为1还是2；
        cin >> l >> x >> y;
        //首先判断是否为题目中所给2 ， 3 的假话（首先判断是否为假话）
        if( x > n || y > n ||(( l == 2)&&(x == y))) res ++;
        else
        {
            if( l == 1 )
            {
                int px = find(x);
                int py = find(y);
                if( px == py && (d[x] - d[y]) % 3 != 0) res ++;
                else{
                    if(px != py) {
                        //如果二者不在同一个并查集下，证明并没有真话同时提到
                        //所以这句话是真话
                        p[px] = py ;
                        d[px] = d[y] - d[x];
                    }else
                    {
                        //if(px == py && (d[x] - d[y]) % 3 == 0) //证明说的是真话，不做操作；
                    }
                } 
            }
            else if(l == 2)
            {
                int px = find(x);
                int py = find(y);//第0代，第一代，第二代，第三（0）代，后一代吃前一代
                if( px == py && (d[x] - d[y] - 1) % 3 != 0)
                {
                    res ++;
                }
                else
                {
                    if(px != py)
                    {
                        p[px] = py ;
                        d[px] = d[y] - d[x] + 1;
                    }
                }
            }
        }
    }
    cout << res << endl;
}