题解 | #食物链#

食物链

https://ac.nowcoder.com/acm/problem/16884

链接：https://ac.nowcoder.com/acm/contest/22904/1024
来源：牛客网

题目描述

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。

现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这N个动物所构成的食物链关系进行描述：

第一种说法是“1 X Y”，表示X和Y是同类。

第二种说法是“2 X Y”，表示X吃Y。

此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1）当前的话与前面的某些真的话冲突，就是假话；

2）当前的话中X或Y比N大，就是假话；

3）当前的话表示X吃X，就是假话。

你的任务是根据给定的N（1≤N≤50,000）和K句话（0≤K≤100,000），输出假话的总数。

输入描述:

第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。

输出描述:

只有一个整数，表示假话的数目。

可以用带权并查集或者是种类并查集（完全合并）来做。

种类并查集做法思路：大致做法就是开n的3倍的空间，分别用来存储与自己同级的一类(1~n)，能把对方吃掉的一类(n+1~2n)，会被对方吃掉的一类(2n+1~3n)

当d=1时，判断a与b是否为一类，可以从其反面出发判断，即判断a与b+n或a与b+2n是否为一类，若两者之中任意一个是，则a与b不为一类，如果两者全否，则a与b为一类

当d=2时，判断a吃b是否成立，可以从其反面出发判断，即判断a与b或a与b+2n是否为一类，若两者之中任意一个是，则a吃b不成立，如果两者全否，则a吃b成立

种类并查集（完全合并）代码如下：

#include<stdio.h>

#include<bits/stdc++.h>
using namespace std;
int father[150020]; //开三倍空间存储
int find(int x){ //查找函数
    if(father[x]==x) return x;
    else return father[x]=find(father[x]);
}
void merge(int a,int b){ //合并函数
    if(find(a)!=find(b)) father[find(a)]=find(b);
}
int main(){
    int i,n,k,d,x,y,ans=0;
    scanf("%d %d",&n,&k);
    for(i=1;i<=3*n;i++){
        father[i]=i; //初始化
    }
    while(k--){
        scanf("%d %d %d",&d,&x,&y);
        if(x<=n && y<=n){
            if(d==1){
                if(find(x)!=find(y+n) && find(x)!=find(y+2*n)){ //注意需要三个merge函数，因为三个地方都要合并
                    merge(x,y);
                    merge(x+n,y+n);
                    merge(x+2*n,y+2*n);
                }
                else{
                    ans++;
                }
            }
            if(d==2){
                if(x!=y){
                    if(find(x)!=find(y) && find(x)!=find(y+2*n)){ //注意需要三个merge函数，因为三个地方都要合并
                        merge(x,y+n);
                        merge(x+n,y+2*n);
                        merge(x+2*n,y);
                    }else{
                        ans++;
                    }
                }else{
                    ans++;
                }
            }
        }else{
            ans++;
        }
    }
    printf("%d\n",ans); //输出假话数量
    return 0;

}

带权并查集：概念不细讲，自己查

思路（可以看食物链 _牛客博客这一篇博客）：

设val=0时，a与b同级；val=1时，a吃b；val=2时，a被b吃（因为题目里d为1时同级，2时a吃b，所以下面merge函数里val=d-1）

对于merge（合并）函数，其作用是合并a与b

这里注意一点，设pa,pb分别为a,b的父节点，若pa!=pb，那这一句肯定是真话。

理由如下：

由于merge函数的执行条件是前面判断这句话是否为真话的2和3都成立了（见主函数内代码），也就是说merge函数内部只要判断条件1是否成立就行了。

所以可以看出，若pa!=pb，即a的父节点和b的父节点不相同，这只有一种可能，就是前面的话语中未涉及a和b。因为如果前面的句子涉及到a与b，那么a与b一定已经在那个句子合并了，那么pa就和pb相等了。

所以不管是“a的种类与b相同”还是"a吃b"都肯定是成立的（因为在这句话的前面没有能够证明这句话为假话的话）

带权并查集代码如下：

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int father[50020],value[50020],ans=0; //父节点，权值
int find(int x) { //查找父节点
    if(x!=father[x]) {
        int t=father[x];
        father[x]=find(father[x]);
        value[x]=(value[x]+value[t])%3;
    }
    return father[x];
}
void merge(int a,int b,int val) { //合并a与b(如果符合前面全部的真话所说的),注意val为a和b之间的关系，是虚线不是实线（没连起来）
    int pa=find(a),pb=find(b); //pa,pb为a,b的父节点，找父节点的目的是为了合并
    if(pa!=pb) { //a与b父节点不同（未合并）-->肯定是真话
        father[pa]=pb; //合并a的父节点与b的父节点
        value[pa]=(-value[a]+value[b]+val)%3; //更新a的父节点到b的父节点的权值（即连接pa与pb）
    }else{ //已经合并了，就验证关系是否成立（验证是否是真话）
        if(val!=(value[a]-value[b]+3)%3) ans++; //不符合给定的关系（一种为val=0，即这句话说a与b同级，但a与b之间的关系不是同级；另一种为val=1，即这句话说a吃b成立，但a吃b不成立）,ans+1;
    }
}
int main() {
    int n,k,d,a,b;
    scanf("%d %d",&n,&k);
    for(int i=1; i<=n; i++) father[i]=i; //初始化父节点
    while(k--) {
        scanf("%d %d %d",&d,&a,&b);
        if(a<=n && b<=n) {
            if(d==1) {
                merge(a,b,d-1); //合并a与b
            }
            if(d==2) {
                if(a!=b){
                    merge(a,b,d-1); //合并a与b
                }else ans++;
            }
        }else ans++;
    }
    printf("%d\n",ans);
    return 0;
}

算法入门班习题题解&感悟文章被收录于专栏

这是本人对于算法入门班共十三章习题的题解与个人的一些感悟，本人写题解的目的是对于某些经典的/陌生的/无从下手的/思维方向错误的题目加深印象。希望自己能够在学习算法的路上走得更远，今天也是努力学习的一天!