YeungYeah 的乱写地

并查集

 Posts  

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。

有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作:

  • Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
  • Union：将两个子集合并成同一个集合。

思路

开数组记录每个元素的从属情况，find操作返回元素从属情况，union操作修改其中一个元素的从属情况，将其合并

代码

最简单模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int set[1000];

void init(){
    for(int i<0;i<size;i++) set[i]=i;
}

int find(int x){
    return x==set[x]?x:find(set[x]);
}

int union(int x,int y){
    set[x] = y;
}

最简单的情况下没有任何优化，易退化成链状查询，查询复杂度到达$O(n)$

优化模板

添加路径压缩，减少查询时间

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

int Find(int x)//使用递归写find函数，同时有路径压缩
{
    int a;
    a=x;
    while(set[a]!=a)///循环方法查找前导点
    {
        a=set[a];
    }
    int i=x,j;
    while(i!=a)///路径压缩,修改历经的前导点
    {
        j=set[i];///记录x的前导结点
        set[i]=a;///将i的前导结点设置为r的根节点.
        i=j;
    }
    return a;

}

void Union(int x,int y)
{
    int a,b;
    a=Find(x);///x的根节点为a
    b=Find(y);///y的根节点为b
    if(a!=b)///如果a,b不是相同的根节点，则说明ab不是连通的
    {
        set[a]=b;///将a,b连接，将a的前导点设置为b
    }
}

实例

  • 图的连通性问题：将所有节点合并邻接节点，判断是否属于同一集合
  • 重复数据合并/关联

相关文章：