这是一道分类并查集的题目。
我们要根据题目的要求，求出谎话的数目。题目给了我们一些明确的判断标准：
但是我们会发现，如果只按照这三个条件和普通的并查集，我们只能得30分。
30分做法：我们可以用普通并查集和一个表示谁是谁的食物的数组来完成。
30分代码：
#include<bits/stdc++.h> #define R register int #define M 500500 using namespace std; int n,k,fa[M],ans,eat[M]; inline int find(int x){return fa[x]= fa[x]==x ? x : find(fa[x]);} int main(){ ios::sync_with_stdio(0); int q,x,y; cin>>n>>k; for(R i=1;i<=n;++i) fa[i]=i; for(R i=1;i<=k;++i){ cin>>q>>x>>y; if(x>n || y>n) ++ans; else if(q==1){ if(eat[x]==y || eat[y]==x) ++ans; else if(find(x)!=find(y)) fa[find(x)]=find(y); } else{ if(x==y || eat[y]==x || find(x)==find(y) || eat[x]!=0) ++ans; else eat[x]=y; } } printf("%d",ans); return 0; }
满分做法：
当我们再次仔细读题，就会发现，题目中是有几条隐含在题意里面的判断条件的。
从这里我们可以看出一共只有3种动物，而且食物链是一个环。那么我们就可以得出这样一条关系：如果x的食物是y，那么y的天敌是x，x的天敌是y的食物。这样的话很显然，一个数组是无法完成判断的。而且我们并不知道，x和y分别是哪一种动物。
这时候我们就可以用种类并查集来实现这道题。种类并查集可以用来处理维护一些对立的关系，比如：敌人的敌人是朋友。我们通常会把并查集数组扩大n倍，n就是种类。所以这道题我们就可以开三倍的并查集数组，1到n表示种类A，n+1到n*2表示种类B，n*2+1到n*3表示种类C。然后我们就可以在合并的过程中维护各个点的信息了。
还有部分解释在写在代码注释里了哦↓ ↓ ↓ ↓ ↓ ↓ ↓
满分代码：
#include<bits/stdc++.h> #define R register int #define M 500500 using namespace std; int n,k,fa[M],ans; //n表示同类 n+n表示食物 n+n+n表示天敌 inline int find(int x){return fa[x]= fa[x]==x ? x : find(fa[x]);} inline void unity(int x,int y){fa[find(x)]=find(y);} int main(){ ios::sync_with_stdio(0); int q,x,y; cin>>n>>k; for(R i=1;i<=n*3;++i) fa[i]=i; for(R i=1;i<=k;++i){ cin>>q>>x>>y; if(x>n || y>n) ++ans; else if(q==1){ if(find(x+n)==find(y) || find(x+(n<<1))==find(y)) ++ans; //判断x是y的同类是假话：y是x的食物 , y是x的天敌 else unity(x,y),unity(x+n,y+n),unity(x+(n<<1),y+(n<<1)); //如果x和y是同一个种类：那么x和y是同一种类,x和y的食物是同一种类,x和y的天敌是同一种类 } else{ if(x==y || find(x)==find(y) || find(x)==find(y+n)) ++ans; //判断x吃y是假话：x能吃x(题目要求),x和y是同类的,x是y的食物 else unity(x,y+(n<<1)),unity(x+n,y),unity(x+(n<<1),y+n); //如果x吃y：y的天敌是x,y是x的食物,x的天敌是y的食物(因为一共只有三种动物,而且食物链是一个环形的,不理解的看一下代码后面的图片) } } printf("%d",ans); return 0; }
