【NOI 2001】食物鍊

【題目】

題目傳送門食物鍊

題目背景：

來源：NOI 2001 DAY1 T1

題目描述：

動物王國中有三類動物 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），輸出假話的總數。

輸入格式：

第一行是兩個整數 N 和 K ，以一個空格分隔。

以下 K 行每行是三個正整數 D，X，Y，兩數之間用一個空格隔開，其中 D 表示說法的種類。

若 D=1，則表示 X 和 Y 是同類。

若 D=2，則表示 X 吃 Y 。

輸出格式：

隻有一個整數，表示假話的數目。

樣例資料：

輸入

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5      

輸出

3      

備注：

【樣例說明】

對 7 句話的分析如下：

1 101 1 假話

2 1 2 真話

2 2 3 真話

2 3 3 假話

1 1 3 假話

2 3 1 真話

1 5 5 真話

【分析】

其實這道題我一開始有點思路，想到一半卡住了，看了題解之後瞬間明白了

就是說對于一個動物 x，我們記錄一下它的食物和天敵（為了友善我們分别用 x + n 和 x + 2 * n 表示）

要注意一下 x 的食物的食物是 x 的天敵，x 的天敵的天敵是 x 的食物

然後就是并查集操作啦，具體的解釋就看代碼吧

【代碼】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50005
using namespace std;
int father[3*N];   //要開3倍空間 
int find(int x)
{
	if(father[x]!=x)
	  father[x]=find(father[x]);
	return father[x];
}
void merge(int x,int y)      //合并x,y 
{
	x=find(x);
	y=find(y);
	father[x]=y;
}
int main()
{
	int n,k,i,s,x,y,ans=0;
	scanf("%d%d",&n,&k);
	for(i=1;i<=3*n;++i)      //初始化 
	  father[i]=i;
	for(i=1;i<=k;++i)
	{
		scanf("%d%d%d",&s,&x,&y);
		if(x>n||y>n)  {ans++;continue;}
		//如果x>n或者y>n，那麼是假話 
		if(s==1)   //x,y是同類 
		{
			if(find(x+n)==find(y)||find(x+2*n)==find(y))  {ans++;continue;}
			//如果x是y的食物，或者x是y的天敵，那麼是假話 
			merge(x,y);merge(x+n,y+n);merge(x+2*n,y+2*n);
			//x和y是同類，x的食物和y的食物是同類，x的天敵和y的天敵是同類 
		}
		if(s==2)   //x吃y 
		{
			if(find(x)==find(y)||find(x+2*n)==find(y))  {ans++;continue;}
			//如果x吃x，或者x的天敵是y，那麼是假話 
			merge(x,y+2*n);merge(x+n,y);merge(x+2*n,y+n);
			//x和y的天敵是同類，x的食物和y是同類，x的天敵和y的食物是同類 
		}
	}
	printf("%d",ans);
	return 0;
}