思路：并查集，因为一开始我们并不知道每一只动物是哪一个种类的，所以我们干脆建立三倍于n的空间，1~n这三分之一用来存第i只动物是A的情况，n+1~2n这三分之一用来存第(i-n)只动物是B的情况，2n+1~3n这三分之一用来存这只动物是C的情况。对于每一句话给出的关系，我们并不知道其中的两个动物分别是属于哪一个种类的，所以我们就把每一种情况都处理一遍。当两个属于同一个区间的动物被合并时，就代表它们是同一个种类的；当两个属于不同区间的动物被合并时，就代表作为父节点的那一只动物吃作为子节点的那一只动物。照这样处理每一句真话即可。判断假话时，第2、3种假话是很容易判断的，若是第一种假话就这样判断：如果说的是x与y是同类的话，就判断x有没有和不在同一区间的y合并（这代表x吃y）以及y有没有和不在同一区间的x合并（这代表y吃x），如果有，这就是假话；如果说的是x吃y，就判断x有没有和在同一区间的y合并（这代表x和y是同类）以及y有没有和不在同一区间的x合并（这代表y吃x），如果有，这就是假话。最后输出答案即可。
#include#include #include #include #include #include using namespace std; int f[150005];//f[1~n]存动物A，f[n+1~2n]存动物B，f[2n+1~3n]存动物C int find_(int x)//并查集找祖先函数 { if(f[x]==x) return x;//找到了祖先就返回祖先是哪一个 return f[x]=find_(f[x]);//路径压缩+查找 }void merge_(int x,int y)//并查集合并函数 { int t1=find_(x),t2=find_(y);//找各自的祖先 if(t1!=t2) f[t2]=t1;//如果不在同一个集合内就合并 return;//结束 }int main(){ int n=0,k=0,ans=0; scanf("%d%d",&n,&k); for(int i=1;i<=n*3;i++) f[i]=i;//并查集初始化 for(int i=1;i<=k;i++) { int s=0,x=0,y=0; scanf("%d%d%d",&s,&x,&y); if(x>n||y>n||s==2&&x==y) ans++;//判断属于第2、3种情况的假话 else if(s==1)//如果此句话说的是x和y为同类 //如果前面的话中已经出现x吃y或y吃x的情况，就说明它们不是同类且这一句话是假话 if(find_(x)==find_(y+n)||find_(y)==find_(x+n)) ans++; else//否则就说明这一句话是真的 { //考虑3种情况 merge_(x,y);//若它们均为动物A，则合并x，y merge_(x+n,y+n);//若它们均为动物B，则合并x+n，y+n merge_(x+n*2,y+n*2);//若它们均为动物B，则合并x+n*2，y+n*2 } else//如果此句话说的是x吃y //如果前面的话中已经出现x与y是同类或y吃x的情况，就说明x不吃y且这一句话是假话 if(find_(x)==find_(y)||find_(y)==find_(x+n)) ans++; else//否则就说明这一句话是真的 { //考虑3种情况 merge_(x,y+n);//若x为A且y为B，将y+n合并到x下，表示x吃y+n merge_(x+n,y+n*2);//若x为B且y为C，将y+n*2合并到x+n下，表示x+n吃y+n*2 merge_(x+n*2,y);//若x为C且y为A，将y合并到x+n*2下，表示x+n*2吃y } } printf("%d",ans);//输出 return 0;}