Description

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

Input

第一行是兩個整數N和K，以一個空格分隔。?
以下K行每行是三個正整數 D，X，Y，兩數之間用一個空格隔開，其中D表示說法的種類。?
若D=1，則表示X和Y是同類。?
若D=2，則表示X吃Y。

Output

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

一道特別妙的并查集，寫完就順手弄上來了

用并查集保存x與y之間是否有關，在處理關系時運用了一點小技巧

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> using namespace std; const double pi=sqrt(5.0); using namespace std; int re[100005]; int f[100005]; int n; //re[x]=0 表示f[x]與x同類；1表示f[x]吃x；2表示x吃f[x]。 void init() {for(int i=0;i<n;i++)re[i]=0,f[i]=i; } int found(int x) {if(x!=f[x]){int temp=f[x];f[x]=found(temp);re[x]=(re[x]+re[temp])%3;}return f[x]; } int main() {int k,d,x,y;int ans=0;scanf("%d %d",&n,&k);init();while(k--){scanf("%d %d %d",&d,&x,&y);if(x>n||y>n){ans++;continue;}if(d==2&&x==y){ans++;continue;}int lx=found(x);int ly=found(y);if(lx==ly){if(d==1&&re[x]!=re[y]) ans++;else if(d==2&&re[x]!=(re[y]+2)%3) ans++;//re[x]=2,re[y]=0||re[x]=0,re[y]=1||re[x]=1,re[y]=2}else{f[ly]=lx;re[ly]=(re[x]+3-re[y]+d-1)%3;}}printf("%d\n",ans); }

總結

以上是生活随笔為你收集整理的POJ-1182 食物链的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。