种类并查集

E - A Bug's Life POJ - 2492

E - 食物链 POJ - 1182

种类并查集总归一个思想，就是把一堆的东西分为一些种类，但实际上，每个东西的种类并不确定，强行给它确定一个种类的会不好处理，因为它本身的不确定性。但是如果把他们归到一个集合里，有一个共同的根节点，当要判断某两个东西的关系时，就可以根据他们跟根节点的关系判断。就以食物链这题举例。

题目大意就是，三类动物A吃B，B吃C，C吃A这么一个食物链，然后是有一堆动物并不确定他们是哪类动物，有个人说它们之间的关系，然后判断这个人说的假话有多少句。

跟之前的思路，真话就它们归到一个根节点，而它们和根节点的关系有3种同类，吃，被吃，关键的处理就在于路径压缩以及和根节点的关系，还有判定是不是假话。假如就设定一个动物和它根节点的关系为，0跟根节点同类 1被根节点吃 2吃根节点，那么在路径压缩时，

假如根节点是A，那么A<--B<--C,那么A<--C的关系是？通过观察可以发现00->0 01->1 02->2 10->1 11->2 12->0 20->2 21->0 22->1，C与A的关系是由C与B的关系还有B与A的关系决定的，在这个问题中就有，当前点与根节点关系=（当前点与目前的上一节点的关系+目前的上一节点与根节点关系）%3 。

那在两个动物的根节点连接在一起时该怎么确定，其中一方跟根节点的关系呢？这就需要向量加法假设B是根节点是A,D的根节点的C,加入要把C连到A,C与A的关系就有

A ← C

↑ ↑

B ← D

其中D到B的关系是给出的0或1，代表D与B是同类或D被B吃，B与A,D与C的关系都确定，再要求C与A的关系，其实可以很直观的看出，就是C到D 的关系D到B的关系然后B到A的关系这样这个向量加法，所以A ← C就是C→D加D->B加B->A，D->C的关系逆过来就是C->D了。同样，若已经知道AB是同一根节点要判断是不是假话，也是可以利用向量加法。

 1 #include<stdio.h>
 2 struct Animal{
 3     int root,is;//0跟根节点同类 1被根节点吃 2吃根节点 
 4 }A[51108];
 5 int gui(int x);
 6 int bing(int z,int x,int y);
 7 int main()
 8 {
 9     int i,n,m;
10     scanf("%d%d",&n,&m);
11     for(i=1;i<=n;i++)
12     {
13         A[i].root=i;//根节点初始为自己 
14         A[i].is=0;//自己是自己的同类 
15     }
16     int x,y,z,ans=0;
17     while(m--)
18     {
19         scanf("%d%d%d",&z,&x,&y);
20         if(x>n||y>n)
21             ans++;
22         else if(z==2&&x==y)
23             ans++;
24         else
25             ans+=bing(z,x,y); 
26     }
27     printf("%d
",ans);
28 }
29 int gui(int x)
30 {
31     if(A[x].root==x)
32         return x;
33     int y=A[x].root,z=gui(A[x].root);//注意要先调整上一节点与根节点的关系再来调整
34     A[x].is=(A[x].is+A[y].is)%3;//处理他们的关系 
35     return A[x].root=z;
36 }
37 int bing(int z,int x,int y)
38 {
39     int bx=gui(x),by=gui(y);
40     if(bx==by)//X和Y有公共根节点，代表之前有真话把他们联系在一起，此时方能判断真假 
41     {
42         if((A[y].is+3-A[x].is)%3!=z-1)//与公共根节点的关系判断话的真假 
43             return 1;
44     }//z-1就分别代表0 1 就xy同类还有y被x吃 
45     else
46     {
47         A[by].root=bx;
48         A[by].is=(A[x].is+3-A[y].is+z-1)%3;//向量加法 
49     }
50     return 0;
51 }