【POJ No. 1182】 食物链

【POJ No. 1182】 食物链

POJ 题目地址

【题意】

在动物王国中有三类动物A、B、C，这三类动物的食物链构成了有趣的环形：A吃B，B吃C，C吃A。现有N 个动物，编号为1～N 。每个动物都是A、B、C中的一种。食物链关系有两种描述：1 X Y ，表示X 、Y 是同类；2 X Y ，表示X 吃Y 。

对N 个动物，用上述两种描述方式说出K 句话，这K 句话有的是真的，有的是假的。

一句话满足以下三个条件之一时，就是假话，否则是真话：

• ①当前的话与前面的某些真话冲突；
• ②在当前的话中X 或Y 比N 大；
• ③当前的话表示X 吃X 。请确定假话的数量。

【输入输出】

输入：

第1行包含两个整数N （1≤N ≤50,000）和K （0≤K≤100,000）。在以下K 行中，每行都包含三个正整数C 、X 、Y ，其中C 表示食物链关系描述的种类，C =1或2。

输出：

单行输出假话的数量。

【样例】

【思路分析】

可以使用并查集来查询和合并食物链中动物间的关系。fa[i ]表示第i 个动物的集合号；d [i ]表示第i 个动物在食物链中的深度；在c x y 中，c 表示食物链关系的种类，c =1表示x、y 是同类，c =2表示x 吃y 。

并查集的基本操作是相同的，因为本题用深度来表达动物在食物链中的关系，所以需要考虑3个问题：

• 查找时如何更新深度？
• 合并时如何更新深度？
• 深度满足什么关系是真话？

下面分别进行解答。

① 查找时如何更新深度。

首先找祖宗，集合号等于自身时回归，在回归过程中需要更新集合号为祖宗的集合号，更新当前节点的深度累加其父节点的深度。但是本题只有三种类型的动物，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。也就是说，深度只可以是0、1、2，因此若深度等于3，则将深度转换为0（模3运算）。当前节点的深度累加其父节点的深度模3运算，即d [x ]=(d [x]+d[fx])%3。当输入1吃2、2吃3、3吃4时，并查集如下图中左图所示。当查询1的集合号时，首先找到祖宗4，回归时更新3号节点的深度为1，集合号为4；更新2号节点的深度为2，集合号为4；更新1号节点的深度为0，集合号为4，如下图中右图所示。

② 合并时如何更新深度。

假设x 的集合号为a ，y 的集合号为b，若a ≠b ，则合并集合号fa[a ]=b ，更新a 的深度d [a ]=(d [y ]-d [x ]+3+c -1)%3。因为该食物链为环形，所以需要取模运算，为避免减法出现负值，进行减法运算后加上3然后取模运算即可。输入6吃2，两个节点属于不同的集合7、4，执行合并，fa[7]=4。更新7的深度为d[7]=(d [2]-d [6]+3+2-1)%3=2。合并更新后如下图所示。

当下次查询6的集合号时，找到祖宗4，回归时更新6的深度为d[6]=(d [6]+d [7])%3=0，查询更新后如下图所示。同1、2号节点的关系表达一致，深度d =0的节点吃d =2的节点。

③ 深度满足什么关系是真话。

同一集合中的两个节点x、y 若是同类，则深度差为0；若是x 吃y ，则深度差d [x ]-d [y ]=1或者d [x]-d [y ]=-2。如上图所示，1吃2，高度差为-2；2吃3，高度差为1；3吃1，高度差为1。当高度差为-2时，令其加3，转换为1。当高差为1时，加3变成了4，为了统一，将结果模3即可，若x 吃y ，则(d [x ]-d[y ]+3)%3=1。在c x y 指令中，c =1表示x、y 是同类，c =2表示x吃y 。令c -1，同类时c -1=0，x 吃y 时c- 1=1，因此无论是同类还是吃的关系，公式统一为(d [x ]-d [y ]+3)%3=c -1。若不满足此关系，则为假话。

【算法设计】

① 若x 或y 大于n ，或者x 吃y （x =y ），则为假话。

② 执行c x y 指令时，首先查询x 、y 的集合号。查询集合号回归时，更新路径上每个节点的深度，d [x ]=(d [x ]+d [fx])%3。若x 的集合号为a ，y 的集合号为b ，则分以下两种情况。

• a ≠b ：合并集合号fa[a ]=b ，更新a 的深度d [a ]=(d [y ]-d [x ]+3+c -1)%3。
• a =b ：若(d [x ]-d [y ]+3)%3!=c -1，则为假话。

【举个栗子】

① 合并。2 1 2：1吃2。首先找到1和2所在的集合号1、2，两个集合号不等，将1的集合号修改为2，更新d [1]=(d [2]-d [1]+3+2-1)%3=1。

② 合并。2 2 3：2吃3。首先找到2和3所在的集合号2、3，两个集合号不等，将2的集合号修改为3，更新d [2]=(d [3]-d [2]+2-1+3)%3=1。

③ 查询。1 1 3：查询1和3是同类。首先查询1的集合号，在查询过程中，1的父节点为2，2的父节点为3，3的父节点为3，更新1的集合号等于父节点的集合号3，将当前节点的d 值加上其父节点的d 值，d[1]+=d [2]=2。回归时集合号统一为3，1的集合号和3的集合号相等，但它们是不是同类呢？若满足(d [x ]-d [y ]+3)%3=0，则是同类，否则不是同类。也就是说，当集合号相等时，若x 、y 为同类，则它们的d 值之差加3模3后为0。此时(d [1]-d [3]+3)%3=2，因此为假话。

④ 合并。2 3 1：3吃1。首先找到3和1所在的集合祖宗3、3，两个集合号相等，若满足(d [x ]-d [y ]+3)%3=1，就是真话，也就是说，当集合号相等时，若x 吃y ，则它们的d 值之差加3模3后为1。此时(d [3]-d [1]+3)%3=1，是真话。

⑤ 查询。1 5 5：查询5和5是否是同类。首先查询到5和5的集合号均为5，集合号相等，若满足(d [x ]-d [y ]+3)%3=0，则是同类，否则不是同类。此时(d [5]-d [5]+3)%3=0，是真话。

⑥ 合并。2 5 2：5吃2。首先找到5和2所在的集合祖宗5、3，两个集合号不等，将5的集合号修改为3，更新d [5]=(d [2]-d [5]+2-1+3)%3=2。

⑦ 合并。2 6 1：6吃1。首先找到6和1所在的集合祖宗6、3，两个集合号不等，将6的集合号修改为3，更新d [6]=(d [1]-d [6]+2-1+3)%3=0。

⑧ 合并。2 3 7：3吃7。首先找到3和7所在的集合祖宗3、7，两个集合号不等，将3的集合号修改为7，更新d [3]=(d [7]-d [3]+2-1+3)%3=1，如下图中左图所示。下次查询6时，会更新从6到祖宗7的所有节点的集合号和d 值，如下图中右图所示。

【算法实现】

① 初始化。

void Init(){ //初始化 集合号及深度
	for(int i = 1; i <= n ; i++){
		fa[i] = i;
		d[i] = 0;
	}
}
1
2
3
4
5
6

② 查找集合号。查询x 、y 的集合号，在返回过程中，除了统一集合号，还需要更新d 值（将当前节点的d 值累加其父节点的d 值模3）。

int Find(int x){ //查找
	int fx = fa[x];
	if(x != fa[x]){
		fa[x] = Find(fa[x]);
		d[x] = (d[x] + d[fx]) % 3; //更新x 的深度
	}
	return fa[x];
}
1
2
3
4
5
6
7
8

③ 判断假话数量。对输入的每条指令，若x 或y 大于n ，或x吃y （x =y ），则为假话，计数器加1；否则查询集合号，若x 的集合号为a ，y 的集合号为b ，则a ≠b 时合并集合号fa[a ]=b ，更新a的深度d [a ]=(d [y ]-d [x ]+3+c -1)%3；在a =b 时进行判断，若(d[x ]-d [y ]+3)%3!=c -1，则为假话。

	while(k--){
		scanf("%d%d%d",&c,&x,&y);
		if(x>n||y>n||(c==2&&x==y))
			total++;
		else{
			a=Find(x),b=Find(y);
			if(a==b){
				if((d[x]-d[y]+3)%3!=c-1)
					total++;
			}
			else{
				fa[a]=b;
				d[a]=(d[y]-d[x]+3+c-1)%3;
			}
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

[完整代码]

#include
#include
using namespace std;
#define N 50010
int n,fa[N],d[N];

void Init(){
	for(int i=1;i<=n;i++){
		fa[i]=i;
		d[i]=0;
	}	
}

int Find(int x){
	int fx=fa[x];
	if(x!=fa[x]){
		fa[x]=Find(fa[x]);
		d[x]=(d[x]+d[fx])%3;
	} 	
    return fa[x];
}

int main(){
	int k,c,x,y,total=0,a,b;
	scanf("%d%d",&n,&k);
	Init();
	while(k--){
		scanf("%d%d%d",&c,&x,&y);
		if(x>n||y>n||(c==2&&x==y))
			total++;
		else{
			a=Find(x),b=Find(y);
			if(a==b){
				if((d[x]-d[y]+3)%3!=c-1)
					total++;
			}
			else{
				fa[a]=b;
				d[a]=(d[y]-d[x]+3+c-1)%3;
			}
		}
	}
	printf("%d\n",total);
	return 0;
}
	

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47