NOI2001 食物鍊 （并查集處理集合）

P1438 [NOI2001]食物鍊 時間: 1000ms / 空間: 131072KiB / Java類名: Main

描述

    動物王國中有三類動物 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。

輸出格式

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

測試樣例1

輸入

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句話的分析 

100 7

1 101 1    假話 

2 1 2      真話 

2 2 3      真話 

2 3 3      假話 

1 1 3      假話 

2 3 1      真話 

1 5 5      真話 NOI 2001 食物鍊(eat) 解析：所有的動物分成三類：a吃b，b吃c，c吃a。           對于動物 i  ，f[i] 表示與動物 i 是同類，f[i+n]表示被 i 吃的那一類動物，f[i+2n]表示吃 i 的那一類動物。接下來就是對每一句話進行處理，（x或y大于n就不細說了），當d==1時，隻要判斷x與y是否是同類即可；當d==2時，判斷x與y+2n是否是同類即可。 代碼：

#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;

const int maxn=5e4;
int n,len,sum=0,f[maxn*3+20];

int getin()
{
  int ans=0;char tmp;
  while(!isdigit(tmp=getchar()));
  do ans=(ans<<3)+(ans<<1)+tmp-'0';
  while(isdigit(tmp=getchar()));
  return ans;
}

int find(int x)
{
  if(f[x]==x)return x;
  return f[x]=find(f[x]);
}

int work(int x,int y)
{
  int rx1=find(x),ry1=find(y);
  if(rx1==ry1)return 0;
  int rx2=find((x+n)%len),ry2=find((y+n)%len);
  if(rx2==ry1)return 1;
  int rx3=find((x+n*2)%len),ry3=find((y+n*2)%len);
  if(rx3==ry1)return 1;
  f[rx1]=ry1,f[rx2]=ry2,f[rx3]=ry3;
  return 0;
}

int main()
{
  int m,i,j,k,d;
  n=getin(),m=getin(),len=n*3;
  for(i=0;i<len;i++)f[i]=i;
  for(k=1;k<=m;k++)
    {
      d=getin(),i=getin(),j=getin();
      if(i>n || j>n){sum++;continue;}
      if(d==1)sum+=work(i-1,j-1);
      else sum+=work(i-1,(j-1+n*2)%len);
	}
  printf("%d\n",sum);
  return 0;
}