种类并查集

2018/07/23 17:08
阅读数 7

E - A Bug's Life POJ - 2492

D - Find them Catch them

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\n",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 }

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部