A Bug’s Life

Time Limit : 20000/10000ms (Java/Other)   Memory Limit : 131072/65536K (Java/Other)

Total Submission(s) : 23   Accepted Submission(s) : 8

  
  
  

   
   
   2
3 3
1 2
2 3
1 3
4 2
1 2
3 4
  
  
  

  
  
  

   
   
   Scenario #1:
Suspicious bugs found!

Scenario #2:
No suspicious bugs found!
  
  
  

种类并查集,以及权并查集需要关注的是向量偏移的操作。

假设出现的情况为已知x与fa的关系，以及y与fa的关系。

有

要去定x与y的关系根据向量的规则x->y=x->fa+fa->y;  即x->y = -(fa->x)+fa->y;

如果出现多个关系需要压缩的时候例如：

在y没有加入的时候，找x与ffa的关系的时候，已知x与fa的关系，以及fa与ffa的关系，即x->ffa = x->fa+fa->ffa;

在y加入的时候，要确定y与ffa的关系，现在已经知道x与ffa 的关系，所以y->ffa = y->x+x->ffa;

本题中为种类并查集，在压缩完路径之后，需要确定y与ffa之间的关系，我们用0表示y与ffa为同性，用1表示y与ffa为异性。所以在最后得到y->ffa的值之后需要对2求余。

void InitSet(int n)<span style="white-space:pre">			</span>//初始化数组 father[]存储父亲节点，rank存储y到ffa之间的向量偏移。{    for(int i = 1; i <= n ; i++)    {        father[i] = i;        rank[i] = 0;    }}int FindSet(int a)<span style="white-space:pre">	</span>//路径压缩，改变向量偏移的操作。{    if(father[a] != a)    {        int t = father[a];<span style="white-space:pre">		</span>//存储父亲节点，在回溯的时候（路径压缩的事后）求当前节点一父节点的向量偏移        father[a] = FindSet(father[a]);        rank[a] = (rank[a] +rank[t])%2;<span style="white-space:pre">	</span>//mod2,以确定与父亲节点的关系。    }    return father[a];}void UnionSet(int a,int b,int d)<span style="white-space:pre">		</span>//加入集合当中。{    int x = FindSet(a);    int y = FindSet(b);    father[x] = y;    rank[x]=(rank[b]-rank[a]+3+d)%2;<span style="white-space:pre">		</span>//如下图}

找fa->fb的关系的话，已知a->fa，a->b,b->fb的关系，那么fa->fb=fa->a+a->b+b->fb;   即fa->fb = -(a->fa)+a->b+b->fb;

今天的文章种类并查集分享到此就结束了，感谢您的阅读。