NOI2001 食物链题解（种类并查集）

题目传送门：洛谷P2024 && gmoj初中1373

大意

有三种动物分别为A，B，C，关系是：A吃B，B吃C，C吃A。给出K句话，表示每个动物的具体关系，问不成立的关系有多少。

思路

这题要用到一种特殊的并查集：种类并查集。
这种并查集分为多个序列，在本题为ABC三个序列，分别为3个种类的动物。

这种方法处理方式也是很奇怪，即如果一个动物和自己群系的另一个动物（序列）有共同祖先的话，说明它和那个动物是同类。
如果一个动物和下一个群系的另一个动物有共同祖先，说明它吃那个动物。
如果一个动物和上一个群系的另一个动物有共同祖先，说明它被那个动物吃。

利用这个规律，我们就可以判断话是否为真了，只需要记住这三点

如果Y吃X，那么X就不可能吃Y
如果Y吃X，那么X就不可能和Y是同类
如果X和Y是同类，那么X就不可能吃Y

再加上题目说的

1） 当前的话与前面的某些真的话冲突，就是假话；

2） 当前的话中X或Y比N大，就是假话；

3） 当前的话表示X吃X，就是假话。

就可以判断是否是假话了。如果不是假话，再判断是否是X吃Y，还是X和Y是同类。
如果X吃Y，就把X和下一个群系的Y连起来，表示X吃Y。（A、B、C都要！！）
如果X和Y是同类，就把X和当前群系的Y连起来，表示X和Y是同类。（A、B、C都要！！）

代码如下

#include <bits/stdc++.h>
using namespace std;
int f[150001],ans=0,n,m,x,y,z;
int find(int x)
{
	if (f[x]==x) return x;
	return f[x]=find(f[x]);
}
void merge(int x, int y)
{
	f[find(x)]=find(y);
}
int main()
{
	cin >> n >> m;
	for (int i = 0 ; i <= 150000 ; ++i)
	{
		f[i]=i;
	}
	for (int i = 0 ; i < m ; ++i)
	{
		cin >> z >> x >> y;
		if (x > n || y > n) ans++;
		else if (z == 2)
		{
			if (find(x)==find(y) || find(x+n)==find(y+n) || find(x+n*2)==find(y+n*2) || find(x)==find(y+n*2) || find(x+n)==find(y) || find(x+n*2)==find(y+n)) {ans++;continue;}
			merge(x,y+n);
			merge(x+n,y+n*2);
			merge(x+n*2,y);
		} else if (z == 1)
		{
			if (find(x)==find(y+n) || find(x+n)==find(y+n*2) || find(x+n*2)==find(y) || find(x)==find(y+n*2) || find(x+n)==find(y) || find(x+n*2)==find(y+n)) {ans++;continue;}
			merge(x,y);
			merge(x+n,y+n);
			merge(x+n*2,y+n*2);
		}
	}
	cout << ans <<endl;
	return 0;
}

其他例题

AcWing【带权并查集】奇偶游戏

写在最后

并查集数组记得开三倍！！！