GitBook

这里写图片描述 这里写图片描述

也是因为OJ问题卡主了几天的一个题 复制一下当时写的时候写的一些想法

不矛盾的情况下 x,y同类 则 xA-yA xB-yB xC-yC 可以合并 x吃y 则 xA-yB xB-yC xC-yA 可以合并

并查集 体现在

把关系可以成立的合并 那么通过查询两元素是否为同一集合 则可推断这一关系是否可以成立 “当前的话与前面的某些真的话冲突,就是假话;”

如果对于当前的话有矛盾的集合关系已经成立 (已经在同一集合) 那么这句话自然是假话

所以可以用并查集的思想来做

这里用到并查集是因为并查集的两个操作 “合并”可以变为一个集合的关系 “判断”在不在同一集合

所以综合以上思考 只需要把每一个动物都分成ABC三种考虑 然后对整体进行并查集操作即可

毕竟是找出假话 所以有的话只要不能判断是错的 便可以把它当成对的 故可以把全部的情况都综合来进行考虑

(也就是说到最后判断出的“假话”是那些一定错的话)

此处把 1~N 设为 可能为A的情况 N+1~N+N 设为 可能为B的情况 N+N+1~N+N+N 设为 可能为C的情况

需要注意的是ABC并非狭义上的固定种类 而是由于ABC都是假定的 所以不存在顺序问题

也就是内心把它理解为 1~N 设为 可能为B的情况 N+1~N+N 设为 可能为C的情况 N+N+1~N+N+N 设为 可能为A的情况 也未尝不可

主要是满足A->B->C->A的三角关系便可以了 这也是为什么程序里两个 关于 D==1 D==2 的if 只判断了 X 不需要对应判断 X+N X+2N 的原因

这一题需要注意的是在POJ上如果使用 while(scanf("%d %d",&N,&K)!=EOF) { } 也就是允许多次输入的话会WA 所以AC代码改成了只允许输入一次 N K

#include<stdio.h>
int par[150150];
int rank[150150];
int find(int m) {
	if(par[m]==m)
		return m;
	else
		return par[m]=find(par[m]);
}
void unite(int x,int y) {
	x=find(x);
	y=find(y);
	if(x==y)
		return;
	if(rank[x]<rank[y])
		par[x]=y;
	else {
		par[y]=x;
		if(rank[x]==rank[y])
			rank[x]++;
	}
}
int main() {
	int N,K;
	scanf("%d %d",&N,&K);
		for(int i=1; i<=3*N; i++) {
			par[i]=i;
			rank[i]=0;
		}
		int cnt=0;
		while(K--) {
			int D,X,Y;
			scanf("%d %d %d",&D,&X,&Y);
			if(X<1||Y<1||X>N||Y>N) {
				cnt++;
				continue;
			}
			if(D==1) {
				if(find(X)==find(Y+N)||find(X)==find(Y+N+N))
					cnt++;
				else {
					unite(X,Y);
					unite(X+N,Y+N);
					unite(X+N+N,Y+N+N);
				}
			} else {
				if(find(X)==find(Y)||find(X)==find(Y+N+N))
					cnt++;
				else {
					unite(X,Y+N);
					unite(X+N,Y+N+N);
					unite(X+N+N,Y);
				}
			}
		}
		printf("%d\n",cnt);
	
	return 0;
}

题目地址: 【POJ】[1182]食物链 因为POJ上述指出的判题问题 所以附一个NYOJ的地址 【NYOJ】[207]食物链 NYOJ这一题写成多组输入不会WA