题目描述

食物链里三种生物，A吃B，B吃C，C吃A；现有n个动物并给他们编号，但我们并不知道每个动物是哪一种，现说出k句话，只包含两种操作，一种是x与y是同类，一种是x吃y；当满足以下三种情况之一时，便是假话：
1. 与前面某句话冲突；
2. X或Y比n大；
3. 一个动物不能吃它自己；

输出假话个数；

样例

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

3

算法1

拆点并查集

拆点并查集就是把一个点拆成多个点，即可以把一个点放在多个并查集中；例本题中有三种关系类型，则可以维护三个并查集，分别是这种动物本身(同类域)、这个动物能吃掉谁(捕食域)、这个动物能被谁吃掉(天敌域)；使用一个数组的0<x<=n来表示同类域，n<x<=2n表示捕食域，2n<x<=3n表示天敌域；

C++ 代码

#include<iostream>
using namespace std;

int p[150007];

int find(int x){
    return p[x] == x ? x : p[x] = find(p[x]);
}

int main()
{
    int n, k;
    cin>>n>>k;
    for(int i = 1; i <= 3*n; ++i) p[i] = i;         //初始化一定要把三个数组全部初始化掉；
    int d, x, y, res = 0;
    while(k--){
        cin>>d>>x>>y;
        if(x > n || y > n) {++res; continue;}       //如果X或Y比n大则为假话
        if(d == 1){
            if(find(x) == find(y+n) || find(x) == find(y+n+n)) {++res; continue;}   //当两个动物是同类时，一个动物y必不可能在x的捕食域或天敌域；
            p[find(x)] = find(y);                   //更新两个动物的同类域；
            p[find(x+n)] = find(y+n);               //x的捕食域同时是y的捕食域；
            p[find(x+n+n)] = find(y+n+n);           //x的天敌域同样是y的天敌域；
        }else{
            if(find(x) == find(y) || find(x) == find(y+n)) {++res; continue;}   //当x可以吃y时，x必然不是y的同类或者在y的捕食域；
            p[find(x)] = find(y+n+n);               //x是y的天敌；
            p[find(x+n)] = find(y);                 //x的捕食域是y的同类域；
            p[find(x+n+n)] = find(y+n);             //x的天敌域是y的捕食域；
        }
    }
    cout<<res<<endl;
    return 0;
}

算法2

加权并查集

加权并查集是在普通并查集的基础上，对每一条边都记录一个额外信息，这个额外信息被称为权值；对于并查集，一般都会有路径压缩，所以对于加权并查集，也有路径压缩，在加权并查集的路径压缩中，对每一个点重新链接到根节点的过程中，要把路径上所有权值加起来(更新权值)；

来点注释便于理解

1. 在本题中，我们有两个数组，一个是并查集数组，其中记录的是下标对应的根节点，另一个是权值数组，记录下标节点到根节点的权值；
2. 所有的动物最后都在一个集合中，通过权值表示其与根节点的关系，而任意两个动物之间的关系可以通过他们与根节点的关系推断出来；
3. 对于权值数组，其权值除三取余就是它与根节点的关系，例par[x] = y, 则 dis[x] % 3 即为x与y的关系， 0 代表x与y是同类，1代表x吃y，2代表x被y吃；
4. 因为带权值之后的边可以看作是向量，则权值运算可以看作是向量运算，对于par[x] = y，dis[x] 记为vec(x,y)或x->y 即x指向y的向量；

C++ 代码

#include<iostream>
using namespace std;

const int N = 5e4+7;
int par[N], dis[N];                 //par[]是并查集数组，dis[]是权值数组；

int find(int x){                    //找到根节点加路径压缩
    if(par[x] == x) return x;
    int tmp = par[x];
    par[x] = find(par[x]);
    dis[x] += dis[tmp];             //路径压缩时每个节点链接到根节点时，其权值更新为路径上所有权值之和；
    return par[x];
}

int main()
{
    ios::sync_with_stdio(false);

    int n, k;
    cin>>n>>k;
    for(int i = 1; i <= n; ++i) par[i] = i;         //并查集数组初始化；
    int d, x, y, res = 0;
    while(k--){
        cin>>d>>x>>y;
        if(x > n || y > n) {++res; continue;}       //编号大于n的假话；
        int vec;                                    //vec表示x指向y的向量x->y；
        if(d == 2){
            if(x == y) {++res; continue;}           //自己吃自己的假话；
            vec = 1;                                //向量x->y值为1表示x吃y；
        }
        else vec = 0;                               //x->y值为0表示x与y是同类；
        int a = find(x), b = find(y);
        if(a == b){
            if(((dis[x] - dis[y]) % 3 + 3) % 3 != vec)
            //a与b相等时，dis[x]-dis[y] = x->a - y->a = x->a + a->y = x->y;再判断其与给出的x->y的是否相同即可判断出是否为假话；
                ++res;
        }
        else{   //若x与y的根节点不同，则它们不在同一集合，需要将两个集合合并起来，同时也需要更新权值；
            par[a] = b;
            dis[a] = dis[y] - dis[x] + vec;
            //dis[y] - dis[x] + vec = y->b - x->a + x->y = a->x + x->y + y->b = a->b = dis[a];
        }
    }
    cout<<res;
    return 0;
}