题目描述

A,B,C三类动物，互相吃，给出m条描述动物之间关系的语句，判断假话有多少（具体见题目）

思路

首先，我们知道，对于描述动物之间关系的语句有两类：
第一类：描述两动物为同一种族
第二类：描述动物a吃动物b

此时我们又知道，整个食物链只存在三类动物

所以，我们的任意两动物之间，只能有三种情况：

同，吃，被吃

是不是很简单的状态？

我们可以选择用0表示同，1表示吃，2表示被吃

这样，对于任意两个动物之间的关系，我们就可以用查并集来实现了！

fa[i]表示i的祖先元素，w[i]表示i和祖先元素的关系

但是，请注意！我们在状态压缩路径的时候，除了要更新fa[i]还要更新w[i]

接下来，我们将会考虑如何判断话的真假

首先，如果正假无法判断，那么就认作是正确的话，并且进行该操作

如果可以判断真假，我们怎么判断呢？

首先，如果可以判断的话，必然是两者已经处于同一集合！

直接问共同祖先！

1，如果是判断是否同类，那么这两个动物对于祖先必然是相同关系的！

2，如果是判断是否相吃，那么我们其实也有很好的办法：

首先， 和祖先同类的（0） 吃 被祖先吃的（1）
被祖先吃的（1） 吃 吃祖先的（2）
吃祖先的（2） 吃 祖先同类的（0）

那么规律就是，w[b] == (w[a]+1)%3 就可以满足！

这是判断，那么我们怎么建立和查询这个查并集呢？

看示例：

a和b是同类

直接爬到b的最高祖先，查一下关系

1，如果b的最高祖先也同类，直接把a作为b的最高的祖先的祖先，权值为0

2，如果w[b]是1，那么还是直接把a作为b的最高的祖先的祖先，权值为2
因为b的祖先吃b，ab同类，那么要把a作为b的祖先的祖先,a肯定是被吃的

3，如果w[b]是2，那么还是直接把a作为b的最高的祖先的祖先，权值为1
因为b的祖先被b吃，ab同类，那么要把a作为b的祖先的祖先,a肯定是吃b的祖先的

所以，又得到啦！这个可以用 (3-w[b])%3 ; 得到，非常简单

a吃b

1，如果w[b]=1，直接把a作为b的最高的祖先的祖先，权值为0
因为b的祖先吃b，而且a吃b，所以同类

2，如果w[b]是0，那么还是直接把a作为b的最高的祖先的祖先，权值为1
因为b的祖先同类b，a吃b，那么要把a作为b的祖先的祖先,b的祖先肯定是被吃的

3，如果w[b]是2，那么还是直接把a作为b的最高的祖先的祖先，权值为2
因为b的祖先被b吃，a吃b，那么要把a作为b的祖先的祖先,a肯定是被吃的（循环）

也可以 开一个数组 ea[3]={1,0,2} ，确实没什么规律hh

那么查询呢？如果直接祖先不是最高祖先呢？

首先还是常见的递归查找，所以在递归回来的时候，更高的祖先必定已经处理好了！

那么，上一级祖先和最高祖先的关系已知，自己和上一级祖先的关系也知道！

1，如果自己和上一级祖先是0，那么上一级祖先与最高祖先的关系与自己和最高祖先的关系相同

2，如果自己和上一级祖先的关系是1，
（1）上级和最高：0 结果 1
（2）上级和最高：1 结果 2
（3）上级和最高：2 结果 0
算法： (w[fa[i]]+1) % 3

3，如果自己和上一级祖先的关系是2
（1）上级和最高：0 结果 2
（2）上级和最高：1 结果 0
（3）上级和最高：2 结果 1
算法：(w[fa[i]]+2) % 3

最后的统一算法是 ： (w[fa[i]]+w[i])%3

于是，我们的添加和查询操作都完成了！开写吧！

(加权查并集) $O(m)$

相信分析，大胆代码！
~^_^~

C++ 代码

#include <iostream>

using namespace std;

const int ea[3]={1,0,2};

int fa[50010],w[50010];
int n,k,jia=0;

int find_fa(int i){
    if(fa[i]==i || fa[fa[i]] == fa[i]) return fa[i];
    int highs=find_fa(fa[i]);
    w[i]=(w[fa[i]]+w[i])%3;
    fa[i]=highs;
    return fa[i];
}

int main(){
    cin >> n >> k;
    for(int i=0;i<=n;i++){
        fa[i]=i;
        w[i]=0;
    }
    while(k--){
        int a,b,c;
        cin >> c >> a >> b;
        //cout << "NOW "<< c << " " << a << " " << b << endl;
        if(b>n || a>n){
            //cout << "Bigger!" << endl;
            jia++;
            continue;
        }
        if(c==1){
            //cout << a<<" same " <<b<< endl;
            int zua=find_fa(a),zub=find_fa(b);
            //cout << a <<"'s zu " << zua << endl;
            //cout << b <<"'s zu " << zub << endl;
            if(zua==zub){  //验证
                if(w[a]==w[b]){
                    continue;
                }else{
                    jia++;
                    continue;
                }
            }else{  //加入
                fa[zub]=a;
                w[zub]=(3-w[b])%3;
                continue;
            }
        }else if(c==2){
            //cout << a << " eat " << b << endl;
            int zua=find_fa(a),zub=find_fa(b);
            //cout << a <<"'s zu " << zua << endl;
            //cout << b <<"'s zu " << zub << endl;
            if(zub==zua){   //判断
                if(w[b] == (w[a]+1)%3){
                    continue;
                }else{
                    jia++;
                    continue;
                }
            }else{   //加入
                fa[zub]=a;
                w[zub]=ea[w[b]];
                continue;
            }
        }
    }
    cout << jia;
    return 0;
}