240. 食物链(并查集+数论)
动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。
A吃B, B吃C,C吃A。
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。现有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和K句话,输出假话的总数。
输入格式
第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。
输出格式
只有一个整数,表示假话的数目。
数据范围
1≤N≤500001≤N≤50000,
0≤K≤1000000≤K≤100000
输入样例:
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输出样例:
3
思路:根据到根节点的距离模3的值分类
三种动物的吃与被吃关系就建立起来了
所以用并查集维护节点到根节点的距离
图一 给d[px]一个合理的值即可
图二 给d[px]一个合理的值即可
代码:import java.util.*; public class Main{ static final int N=100005; static int p[]=new int[N]; static int d[]=new int[N]; static int n,k; static int find(int x){ if(p[x]!=x){ int t=find(p[x]); d[x]+=d[p[x]]; p[x]=t; } return p[x]; } public static void main(String []args){ Scanner scan=new Scanner(System.in); n=scan.nextInt(); k=scan.nextInt(); for(int i=1;i<=n;i++) p[i]=i; int res=0; while(k-->0){ int D=scan.nextInt(); int x=scan.nextInt(); int y=scan.nextInt(); int px=find(x),py=find(y); if(x>n || y>n) res++; else{
//如果是同一类动物 if(D==1){ if(px==py && (d[x]-d[y])%3!=0) res++;//如果两个动物在一个集合中,那么它们到根节点的距离模3肯定相等,即差值模3等于0,不等于0就是假话 else if(px!=py){//如果不在一个集合中 见图1 p[px]=py; d[px]=d[y]-d[x]; } }
//如果不是同一类动物 else{ if(px==py && (d[x]-d[y]-1)%3!=0) res++;//如果两个动物在一个集合中,题意x吃y,那么x到根节点的距离取模肯定是比y到根节点的距离取模大1,所以,d[x]%3同余(d[y]+1)%3,即差值模3等于0 else if(px!=py){//如果不在一个集合中 见图2 p[px]=py; d[px]=d[y]+1-d[x]; } } } } System.out.println(res); } }
更多精彩