POJ-1182 食物链（种类并查集）

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

只有一个整数，表示假话的数目。

Sample Input

Sample Output

两种做法：

第一种：

参考于：https://blog.csdn.net/weixin_43736492/article/details/100031448

一共有三种关系，0，1，2。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 const int maxn=1e5+10;
17 using namespace std;
18 
19 int fa[50005];
20 int re[50005];//表示i和其根结点的关系，0表示同类，1表示i吃根结点,2表示i被根结点吃 
21  
22 void init(int n)
23 {
24     for(int i=0;i<=n;i++)
25         re[i]=0,fa[i]=i;
26 }
27 int Find(int x)//带权并查集 
28 {
29     if(x!=fa[x])
30     {
31         int t=fa[x];
32         fa[x]=Find(fa[x]);
33         re[x]=(re[x]+re[t])%3;
34     }
35     return fa[x];
36 }
37 
38 int main()
39 {
40     #ifdef DEBUG
41     freopen("sample.txt","r",stdin);
42     #endif
43 //    ios_base::sync_with_stdio(false);
44 //    cin.tie(NULL);
45     
46     int n,m;
47     scanf("%d %d",&n,&m);
48     init(n);
49     int ans=0;
50     for(int i=1;i<=m;i++)
51     {
52         int op,a,b;
53         scanf("%d %d %d",&op,&a,&b);
54         if(a>n||b>n||(a==b&&op==2))
55         {
56             ans++; continue;
57         }
58         int aa=Find(a);
59         int bb=Find(b);
60         if(aa==bb)
61         {
62             if((re[a]+op-1-re[b]+3)%3!=0)    //用向量理解，矢量三角形 
63                 ans++;
64         }
65         else
66         {
67             fa[bb]=aa;
68             re[bb]=(re[a]+op-1-re[b]+3)%3;    //用向量理解
69         }
70     }
71     printf("%d
",ans);
72     
73     return 0;
74 }

第二种：

题解 from：https://www.luogu.org/problemnew/solution/P2024

这道题要我们得出假话的数目，如果这就话和之前的话冲突就是假话。

比如说a和b是同类关系，那就把a和b划分到一个集合中，之后再说a和b是捕食关系一定是假话了。但是这道题的问题在于某一个动物在食物链中的角色不是一定的，一个物种可能作为捕食者也可能是被捕食者，还有可能给出同类之间的关系，那该怎么办呢？将所扮演的三种状态全都表示出来。列如，对于物种x，x代表A类，x+n代表B类，x+2*n代表C类，其中A吃B，B吃C，C吃A。

对于两个动物如果是同类关系，那么一定不存在捕食和被捕食关系；如果存在捕食关系，那么一定不存在被捕食和同类关系。

引入

并查集能维护连通性、传递性，通俗地说，亲戚的亲戚是亲戚。

然而当我们需要维护一些对立关系，比如敌人的敌人是朋友时，正常的并查集就很难满足我们的需求。

这时，种类并查集就诞生了。

常见的做法是将原并查集扩大一倍规模，并划分为两个种类。

在同个种类的并查集中合并，和原始的并查集没什么区别，仍然表达他们是朋友这个含义。

考虑在不同种类的并查集中合并的意义，其实就表达他们是敌人这个含义了。

按照并查集美妙的传递性，我们就能具体知道某两个元素到底是敌人还是朋友了。

至于某个元素到底属于两个种类中的哪一个，由于我们不清楚，因此两个种类我们都试试。

这题说到底就是用3倍的并查集的存各种动物的关系

一倍存本身，二倍存猎物，三倍存天敌

唯一容易忽略的点就是：一的猎物的猎物就是一的天敌

那么我们每次只要维护三个并查积的关系就可以了

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 const int maxn=1e5+10;
17 using namespace std;
18 
19 int fa[4*50005];//对于每种生物：设 x为本身，x+n为猎物，x+2*n为天敌
20 
21 void init(int n)
22 {
23     for(int i=1;i<=n;i++)
24         fa[i]=i;
25 }
26  
27 int Find(int x)
28 {
29     return x==fa[x]? x:fa[x]=Find(fa[x]);
30 }
31  
32 void Union(int a,int b)
33 {
34     int aa=Find(a);
35     int bb=Find(b);
36     if(aa!=bb) fa[aa]=bb;
37 }
38 
39 int main()
40 {
41     #ifdef DEBUG
42     freopen("sample.txt","r",stdin);
43     #endif
44 //    ios_base::sync_with_stdio(false);
45 //    cin.tie(NULL);
46     
47     
48     int n,m;
49     scanf("%d %d",&n,&m);
50     init(3*n);
51     int ans=0;
52     for(int i=1;i<=m;i++)
53     {
54         int op,a,b;
55         scanf("%d %d %d",&op,&a,&b);
56         if(a>n||b>n)  //不属于该食物链显然为假
57         {
58             ans++; continue;
59         }
60         if(op==1) //同类关系 
61         {
62             if(Find(a+n)==Find(b)||Find(a+n+n)==Find(b))//如果a是b的猎物或天敌，显然为假 
63                 ans++;
64             else//如果a和b为同类 
65             {
66                 Union(a,b); //a 和 b 在同一个集合 
67                 Union(a+n,b+n); //a的猎物 和 b的猎物 在同一个集合 
68                 Union(a+n+n,b+n+n); //a的天敌 和 b的天敌 在同一个集合 
69             }
70         }
71         else if(op==2) //捕食关系 
72         {
73             if(a==b||Find(a)==Find(b)||Find(a)==Find(b+n)) ans++;//如果a是b的同类或猎物，显然为假 
74             else//如果a捕食b 
75             {
76                 Union(a,b+n+n);        //a 和 b 的天敌在同一个集合里
77                 Union(a+n,b);        //a的猎物 和 b 在同一个集合里 
78                 Union(a+n+n,b+n);    //a的天敌 和 b 的猎物在同一个集合里 
79             }
80         }
81     }
82     printf("%d
",ans);
83     return 0;
84 }