題干：

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

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

Sample Input

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

Sample Output

3

?

解題報告：

其中，在判斷真假話之后如果是真話就必須更新這句真話。

其實判斷此類并查集問題的關鍵是先搞清楚這兩個節點之間的關系。

比如 1 2 3這個操作，如果要你判斷2和3是同類這一個命題。

那么，我們就找2和3相對于祖宗的性質，比如2被其祖宗吃，3吃其祖宗，那么如果2和3是同一個祖宗（同一個集合）顯然這個命題不成立。

如果2和3不是同一個祖宗，那么我們現在就需要合并兩個祖宗，因此打表一下就能得出兩個祖宗之間的關系。

2的操作也是這個原理。

?

貼一份測試數據：POJ - 食物鏈 - 測試數據

?

AC代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm>using namespace std; const int MAX=50000 + 5; int f[MAX]; int rank[MAX]; int n,k,ans; int getf(int x) {if(x!=f[x]) {int tmp=getf(f[x]);rank[x]=(rank[x]+rank[f[x] ] ) % 3;f[x]=tmp;}return f[x]; } bool merge(int d,int x,int y) {int t1=getf(x);int t2=getf(y);if(t1==t2) {if((rank[y]-rank[x]+3)%3!=d)return 1;else return 0;}else {f[t2]=t1;rank[t2]=(rank[x]-rank[y]+d+3) % 3;return 0;}} int main() {int d,u,v;scanf("%d%d",&n,&k);ans=0;//初始化 for(int i=1;i<=n;i++) {f[i]=i;rank[i]=0;}while(k--) {scanf("%d %d %d",&d,&u,&v);if(u>n||v>n||(u==v&&d==2) ) {ans++;continue;}if(merge(d-1,u,v) ) ans++;}printf("%d\n",ans);return 0; }

?

附一個博客的講解：https://blog.csdn.net/c0de4fun/article/details/7318642

Part I ?- 權值(relation)的確定。
? ? 我們根據題意，森林中有3種動物。A吃B，B吃C，C吃A。
? ? 我們還要使用并查集，那么，我們就以動物之間的關系來作為并查集每個節點的
? ? 權值。
? ? 注意，我們不知道所給的動物（題目說了，輸入只給編號）所屬的種類。
? ? 所以，我們可以用動物之間“相對”的關系來確定一個并查集。
? ? 0 - 這個節點與它的父節點是同類
? ? 1 - 這個節點被它的父節點吃
? ? 2 - 這個節點吃它的父節點。
? ? 注意，這個0,1,2所代表的意義不是隨便制定的，我們看題目中的要求。
? ? 說話的時候，第一個數字（下文中，設為d）指定了后面兩種動物的關系：
? ? 1 - X與Y同類
? ? 2 - X吃Y
? ? 我們注意到，當 d = 1的時候，( d - 1 ) = 0，也就是我們制定的意義
? ? ? ? ? ? ? ? 當 d = 2的時候，( d - 1 ) = 1，代表Y被X吃，也是我們指定的意義。
? ? 所以，這個0,1,2不是隨便選的
? ? Part II - 路徑壓縮，以及節點間關系確定
? ? 確定了權值之后，我們要確定有關的操作。
? ? 我們把所有的動物全初始化。
? ? struct Animal
? ? {
? ? ? ? int num; //該節點（node）的編號
? ? ? ? int parent; //該node的父親
? ? ? ? int relation; //該node與父節點的關系，0同類，1被父節點吃，2吃父節點
? ? }; Animal ani[50010];
? ? ? ? 初始化為
? ? ? ? For i = 0 to N do
? ? ? ? ? ? ani[i].num = i;
? ? ? ? ? ? ani[i].parent = i;
? ? ? ? ? ? ani[i].relation = 0 ; //自己和自己是同類
? ? ? ? End For
? ? ? ? (1)路徑壓縮時的節點算法
? ? ? ? 我們設A,B,C動物集合如下：（為了以后便于舉例）
? ? ? ? A = { 1 , 2 , 3 ,4 ,5 }
? ? ? ? B = { 6 , 7 , 8 ,9 ,10}
? ? ? ? C = { 11, 12, 13,14,15}
? ? ? ? 假如我們已經有了一個集合，分別有3個元素
? ? ? ? SET1 = {1,2}，我們規定集合中第一個元素為并查集的“代表”
? ? ? ? 假如現在有語句：
? ? ? ? 2 2 6
? ? ? ? 這是一句真話
? ? ? ? 2是6的父親
? ? ? ? ?ani[6].parent = 2;
? ? ? ? ?ani[6].relation = 1;
? ? ? ? 那么，6和1的關系如何呢？
? ? ? ? ?ani[2].parent = 1;
? ? ? ? ?ani[2].relation = 0;
? ? ? ? 我們可以發現6與2的關系是 1.
? ? ? ? 通過窮舉我們可以發現
? ? ? ? ani[now].parent = ani[ani[now].parent].parent;
? ? ? ? ani[now].relation = ( ani[now].relation + ani[now.parent].relation ) % 3;
? ? ? ? 這個路徑壓縮算法是正確的
? ? ? ? 關于這個路徑壓縮算法，還有一點需要注意的地方，我們一會再談
? ? ? ? 注意，根據當前節點的relation和當前節點父節點的relation推出
? ? ? ? 當前節點與其父節點的父節點的relation這個公式十分重要！！
? ? ? ? 它推不出來下面都理解不了！！自己用窮舉法推一下：
? ? ? ? 好吧，為了方便伸手黨，我給出窮舉過程
? ? ? ? ? ? ? ? i ? ? ?j
? ? ? ? 爺爺 ?父親 ?兒子 ?兒子與爺爺
? ? ? ? ? ? ? ?0 ? ? ?0 ? ? ? (i + j)%3 = 0
? ? ? ? ? ? ? ?0 ? ? ?1 ? ? ? (i + j)%3 = 1
? ? ? ? ? ? ? ?0 ? ? ?2 ? ? ? (i + j)%3 = 2
? ? ? ? ? ? ? ?1 ? ? ?0 ? ? ? (i + j)%3 = 1
? ? ? ? ? ? ? ?1 ? ? ?1 ? ? ? (i + j)%3 = 2
? ? ? ? ? ? ? ?1 ? ? ?2 ? ? ? (i + j)%3 = 0
? ? ? ? ? ? ? ?2 ? ? ?0 ? ? ? (i + j)%3 = 2
? ? ? ? ? ? ? ?2 ? ? ?1 ? ? ? (i + j)%3 = 0
? ? ? ? ? ? ? ?2 ? ? ?2 ? ? ? (i + j)%3 = 1
? ? ? ? 嗯，這樣可以看到，( 兒子relation + 父親relation ) % 3 = 兒子對爺爺的relation
? ? ? ? 這就是路徑壓縮的節點算法
? ? ? ? (2) 集合間關系的確定
? ? ? ? 在初始化的時候，我們看到，每個集合都是一個元素，就是他本身。
? ? ? ? 這時候，每個集合都是自洽的（集合中每個元素都不違反題目的規定）
? ? ? ? 注意，我們使用并查集的目的就是盡量的把路徑壓縮，使之高度盡量矮
? ? ? ? 假設我們已經有一個集合
? ? ? ? set1 = {1,2,7,10}
? ? ? ? set2 = {11,4,8,13},每個編號所屬的物種見上文
? ? ? ? set3 = {12,5,4,9}
? ? ? ? 現在有一句話
? ? ? ? 2 13 2
? ? ? ? 這是一句真話,X = 13,Y = 2
? ? ? ? 我們要把這兩個集合合并成一個集合。
? ? ? ? 直接
? ? ? ? int a = findParent(ani[X]);
? ? ? ? int b = findParent(ani[Y]);
? ? ? ? ani[b].parent = a;
? ? ? ? 就是把Y所在集合的根節點的父親設置成X所在集合的根節點。
? ? ? ? 但是，但是！！！！
? ? ? ? Y所在集合的根結點與X所在集合的根節點的關系！！！要怎么確定呢？
? ? ? ? 我們設X,Y集合都是路徑壓縮過的，高度只有2層
? ? ? ? 我們先給出計算的公式
? ? ? ? ani[b].relation = ( 3 - ani[Y].relation + ( d - 1 ) + ani[X].relation) % 3;
? ? ? ? 這個公式，是分三部分，這么推出來的
? ? ? ? 第一部分，好理解的一部分：
? ? ? ? ( d - 1 ) :這是X和Y之間的relation，X是Y的父節點時，Y的relation就是這個
? ? ? ? 3 - ani[Y].relation = 根據Y與根節點的關系，逆推根節點與Y的關系
? ? ? ? 這部分也是窮舉法推出來的，我們舉例：
? ? ? ? j
? ? ? ? 子 ? ? ? ? 父相對于子的relation（即假如子是父的父節點，那么父的relation應該是什么，因為父現在是根節點，所以父.relation = 0，我們只能根據父的子節點反推子跟父節點的關系）
? ? ? ? ?0 ? ? ? ? ? ? ( 3 - 0 ) % 3 = 0
? ? ? ? ?1（父吃子） ? ( 3 - 1 ) % 3 = 2 //父吃子
? ? ? ? ?2（子吃父) ? ?( 3 - 2 ) % 3 = 1 //子吃父，一樣的哦親
? ? ? ? ——————————————————————————————————————————————————————
? ? ? ? 我們的過程是這樣的：
? ? ? ? 把ani[Y]，先連接到ani[X]上，再把ani[Y]的根節點移動到ani[X]上，最后，把ani[Y]的根節點移動到ani[X]的根節點上，這樣算relation的
? ? ? ? 還記得么，如果我們有一個集合，壓縮路徑的時候父子關系是這么確定的
? ? ? ? ani[爺爺].relation = ( ani[父親].relation + ani[兒子].relation ) % 3
? ? ? ? 我們已知道,( d - 1 )就是X與Y的relation了
? ? ? ? 而 (3 - ani[Y].relation)就是 以Y為根節點時，他的父親的relation
? ? ? ? 那么
? ? ? ? 我們假設把Y接到X上，也就說，現在X是Y的父親，Y原來的根節點現在是Y的兒子
? ? ? ? ? Y的relation ? + ? ? ani[Y]根節點相對于ani[Y]的relation
? ? ? ? ( ( d - 1 ) ? ? ? ? + ? ?( 3 - ani[Y].relation) ) % 3
? ? ? ? 就是ani[Y]的父親節點與ani[X]的relation了！
? ? ? ? 那么，不難得到，ani[Y]的根節點與ani[X]根節點的關系是：
? ? ? ? ( ( d - 1 ) + ( 3 - ani[Y].relation) + ani[X].relation ) % 3 ->應用了同余定理
? ? ? ? 注意，這個當所有集合都是初始化狀態的時候也適用哦
? ? ? ? 還是以最開頭我們給的三個集合（分別代表三個物種）為例
? ? ? ? 2 1 6
? ? ? ? 帶入公式
? ? ? ? ani[6].relation = ( ( 2 - 1 ) + ( 3 - 0 ) + 0 ) % 3 = 1
? ? ? ? 也就是，6被1吃
? ? Part III - 算法正確性的證明
? ? ? ? 首先，兩個自洽的集合，合并以后仍然是自洽的
? ? ? ? 這個不難想吧，數學上有個什么對稱性定理跟他很像的。
? ? ? ? 如果理解不了，就這么想！！
? ? ? ? 當set1和set2合并之后，set2的根節點得到了自己關于set1根節點的
? ? ? ? 正確relation值，變成了set1根節點的兒子，那么
? ? ? ? set2的所有兒子只要用
? ? ? ? ( ani[X].relation + ani[Y].relation ) % 3就能得到自己正確的relation值了
? ? ? ? 所以說，針對不在同一集合的兩個元素的話，除非違背了（2）和（3），否則永遠是真的
? ? ? ? （無論這句話說的是什么，我們都可以根據所給X,Y推出兩個子節點之間應有的關系，這個關系一確定，所有兒子的關系都可以確定）
? ? ? ? 其實所有的不同集合到最后都會被合并成一個集合的。
? ? ? ? 我們只要在一個集合中找那些假話就可以了。
? ? ? ? 首先，如何判斷
? ? ? ? 1 X Y是不是假話。//此時 d = 1
? ? ? ? if ( X 和 Y 不在同一集合)
? ? ? ? ? ? Union(x,y,xroot,yroot,d)
? ? ? ? else
? ? ? ? ? ? if x.relation != y.relation ?->假話
? ? ? ? 其次，如何判斷
? ? ? ? 2 X Y是不是假話 //此時d = 2
? ? ? ? if ( X 和 Y 不在同一集合）
? ? ? ? ? ? Union(x,y,xroot,yroot,d)
? ? ? ? else
? ? ? ? ? ? (ani[y].relation + 3 - ani[x].relation ) % 3 != 1 ->假話
? ? ? ? 這個公式是這么來的：
? ? ? ? 3 - ani[x].relation得到了根節點關于x的relation
? ? ? ? ani[y] + 3 - ani[x].relation得到了y關于x的relation
? ? ? ? 所以，只要y關于x的relation不是1，就是y不被x吃的話，這句話肯定是假話！
? ? ? ? (2)路徑壓縮要特別注意的一點（錯在這里，要檢討自己）
? ? ? ? ? ? 路徑壓縮的時候，記得要
? ? ? ? ? ? 先findParent，再給當前節點的relation賦值。
? ? ? ? ? ? 否則有可能因為當前節點的父節點的relation不正確而導致錯的稀里嘩啦。
? ? ? ? ? ? 例子：
? ? ? ? ? ? set1 = {1,2,7,10}
? ? ? ? ? ? set2 = {3,4,8,11}
? ? ? ? ? ? set3 = {12,5,14,9}
? ? ? ? ? ? Union(1,3,1,3,1)
? ? ? ? ? ? Union(3,12,3,12,2)
? ? ? ? ? ? 1 5 1
? ? ? ? ? ? 算5的relation
? ? ? ? ? ? 如果不先更新parent的relation，算出來應該是
? ? ? ? ? ? ( 3 - 0 + 0 + 1 ) % 3 = 1，5被1吃，顯然不對
? ? ? ? ? ? 這里面，+ 0的那個0是指根節點 12 的relation（未更新，這里的0是指12與11的relation）
? ? ? ? ? ? 如果更新完了的話，應該是
? ? ? ? ? ? ( 3 - 0 + 2 + 1 ) % 3 = 0 ,5與1是同一物種，對了
? ? ? ? ? ? 這里面的 2 是更新節點12的relation（12與1的relation）

#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream>using namespace std; const int c0de4fun = 50010;//動物個數的最大值 ///指明父節點與自己的關系，0同類，1被吃，2吃父 const int SAME = 0; const int ENEMY = 1; const int FOOD = 2; struct Animal {int parent;int num;int relation; }; Animal ani[c0de4fun]; long ans; int findParent(Animal* node) {///Wrong Answer 因為這個函數寫錯了///這個函數得是“自洽的”///就是說，得保證每個元素的父親的relation是對的///再算自己的relation///因為自己的relation和父親的relation有關///這就是為什么要先findParent再relation更新的原因int tmp;if( node->parent == node->num )return node->parent;tmp = node->parent; #ifdef DBGprintf("Animal %d s Parent is %d\n",node->num,node->parent); #endif// node->relation = ( ani[node->parent].relation + node->relation ) % 3;node->parent = findParent(&ani[node->parent]);node->relation = ( ani[tmp].relation + node->relation ) % 3;return node->parent; } void Union(int x,int y,int a,int b,int d) {ani[b].parent = a;///rootY.parent = rootX.parent;ani[b].relation =( (3 - ani[y].relation) + (d - 1) + ani[x].relation) % 3; }void init_Animal(int n) {for(int i = 1 ; i <= n ; i++){ani[i].num = i;ani[i].parent = i;ani[i].relation = SAME;} } int main(int argc,char* argv[]) {int N,K;int d,X,Y; #ifdef INPUTfreopen("b:\\acm\\poj1182\\input.txt","r",stdin); #endifscanf("%d%d",&N,&K);init_Animal(N);for(int i = 0 ; i < K ; i++){scanf("%d%d%d",&d,&X,&Y);if( X > N || Y > N)ans++;else{if(d == 2 && X == Y)ans++;else{int a = findParent(&ani[X]);int b = findParent(&ani[Y]);if ( a != b ){///x，y不在同一集合中Union(X,Y,a,b,d);}else{switch(d){case 1:if(ani[X].relation != ani[Y].relation)ans++;break;case 2:if(((ani[Y].relation + 3 - ani[X].relation) % 3 ) != 1)ans++;break;}}}}}printf("%d\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的【POJ - 1182】 食物链（附超详细讲解）（并查集--种类并查集经典题）的全部內容，希望文章能夠幫你解決所遇到的問題。

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