题目描述
动物王国中有三类动物 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 句话有的是真
的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
• 当前的话与前面的某些真的话冲突,就是假话
• 当前的话中 X 或 Y 比 N 大,就是假话
• 当前的话表示 X 吃 X,就是假话
你的任务是根据给定的 N 和 K 句话,输出假话的总数。
输入输出格式
输入格式:从 eat.in 中输入数据
第一行两个整数,N,K,表示有 N 个动物,K 句话。
第二行开始每行一句话(按照题目要求,见样例)
输出格式:输出到 eat.out 中
一行,一个整数,表示假话的总数。
输入输出样例
说明
1 ≤ N ≤ 5 ∗ 10^4
1 ≤ K ≤ 10^5
带权并查集,f[x][0]存x的父亲,f[x][1]存x与父亲的关系:0表示x与父亲是同类,1为x吃父亲,2为x的父亲吃x(...
可以再每次查询祖先的时候将f数组压缩
原理:将x到树顶的路径f[i][0]加和最后%3即为x与树根关系。
#include<iostream> #include<stdio.h> using namespace std; int i,m,n,j,k,h,g,f[1000001][2],b,ans; int father(int x) { if(f[x][0]==x) { m=f[x][1]; return f[x][0]; } f[x][0]=father(f[x][0]); f[x][1]=(f[x][1]+m+3)%3; m=f[x][1]; return f[x][0]; } int main() { scanf("%d%d",&n,&k); for(i=1;i<=n;i++) f[i][0]=i; for(i=1;i<=k;i++) { scanf("%d%d%d",&b,&g,&h); if((g>n || h>n)||(g==h && b==2)) { ans+=1; continue; } m=0; father(g); m=0; father(h); if(f[g][0]==f[h][0]) { if(b==1) if(f[g][1]!=f[h][1]) ans+=1; if(b==2) if((f[g][1]+2)%3!=f[h][1]) ans+=1; } else { if(b==1) { f[f[g][0]][1]=(f[h][1]+3-f[g][1])%3; f[f[g][0]][0]=f[h][0]; } if(b==2) { f[f[h][0]][1]=(f[g][1]+5-f[h][1])%3; f[f[h][0]][0]=f[g][0]; } } } printf("%d",ans); }