博客

一、带权并查集讲解

1、简介：

• 带权并查集是一种储存
  
  子与根
  
  之间的特定关系的数组，应用范围比普通的并查集更为广泛。这时需要设立个
  
  数组D[]
  
  来维护
  
  子与根
  
  之间的关系。

不多说，直接上图更好理解。

2、普通并查集与带权并查集的区分：

1. 
   普通并查集
   
   是用来维护
   
   相同属性
   
   集合的。
2. 
   带权并查集
   
   可以用来维护
   
   不同属性集合
   
   ，比如性别，上下级关系，食物链关系等等(下面会有例题的讲解)。

3、难点：

问题：

1. 如何在
   
   路径压缩
   
   的时候更新
   
   子与根
   
   之间的关系呢？
2. 如何在
   
   合并
   
   的时候更新两棵树之间
   
   同深度的分支
   
   之间的关系呢？

解决：

1. 
   路径压缩时：
   
   
   
   
   
   伪代码：

int find_set(int x)
{
    if (x != s[x])
    {
        int t=s[x];//x的父
        s[x]=find_set(s[x]);
        d[x]=d[x]与d[t]关系的变化。
    }
    return s[x];
}

2. 
   合并时：
   
   
   

这个时候，来一手向量法求子链之间的关系：




伪代码：

void union_set(int x, int y)
{
    int rootx = find_set(x), rooty = find_set(y);
    if (rootx == rooty)//根相同时
    {
        //符合题干的操作，比如判断正确与否
    }
    else//根不同时
    {
        s[rootx]=rooty;//合并
        d[x]=d[rootx]-d[rooty]+(rootx和rooty之间的关系)；
        //符合题干的操作，更新子链操作(再图解中)
    }
}