【POJ 1182】【并查集】食物链

题目链接:http://poj.org/problem?id=1182

食物链
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 93015 Accepted: 28066

Description

动物王国中有三类动物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),输出假话的总数。

Input

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

Output

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

Sample Input

Sample Output

Source

题目大意:如题。
解法一:带权并查集。
解法二:用集合关系表示同类和捕食关系。
为了便于理解,这三类动物可以解释为分解者,消费者,生产者。
假设消费者捕食生产者,生产者捕食分解者,分解者捕食消费者。(实际上不是这样,这样说只是为了确立三者之间的捕食顺序关系)
n个动物,每个动物可能是三者之一,不妨用[1,n]表示分解者,[n+1, 2n]表示消费者,[2n+1,3n]表示生产者。
定义(a,b)表示动物a和b再同一个集合。
定义a,b为同类的集合关系表现为:(a,b)
定义a捕食b的集合关系表现为:(a,b+n)
定义merge(a,b)为使得a,b 在同一个集合
逐条读入k句话(排除掉显然错误的话),然后:
  • 若断言a,b是同类。我们先判断a,b是否存在捕食或者反捕食关系:是否(a,b+n)和(b,a+n)由于我们不知道a,b是分解者,消费者还是生产者,但是我们知道a,b一定是同一种类型的。所以不妨认为:1,a,b都是分解者;2,a,b都是消费者,3,a,b都是生产者。
  • 若断言a捕食b。我们要判断a,b是否是同类和b是否捕食a。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注