并查集

并查集是什么

顾名思义，并查集就是一种支持合并与查找的集合，它能支持两种操作：

  • 查询元素a和元素b是否在同一集合
  • 合并元素a和元素b所在的集合

并查集的结构

如果我们从每个集合中选出一个元素来代表这个集合，那么它就相当于树的根节点，于是，我们便可以用树形结构来实现并查集。

初始化

1
2
3
4
5
void init(int n)
{
    for(int i = 0; i < n; i++)
        fa[i] = i;
}

意思就是将每棵树的根节点设为自己，即每个元素初始为一个集合

查找

1
2
3
4
5
6
7
int find(int p)
{
    if(fa[p] == p)
        return p;
    else 
        return find(fa[p]);
}

查找过程就是由当前节点开始查询自己的父节点，如果是根节点，就返回根节点的值，代表这个集合；如果不是根节点，就以父节点为起点再进行一次查询，递归得到根节点。由于只与深度有关，所以这一查询过程的时间复杂度为O(logn)O(logn)。

但是我们会发现，随着我们不断的合并，并查集会越来越长，这个时候再想从底部查询到顶部就会需要越来越多的时间。所以，我们可以在每次的查询过程中，将沿途的父节点设为根节点，即路径压缩，这样当我们查询到真正的根节点时，所有的子节点都直接连在了根节点上，下次查询时的复杂的就是O(1)O(1)了。

代码实现：

1
2
3
4
5
6
7
int find(int p)
{
    if(fa[p] == p)
        return p;
    else
        return fa[p] = find(fa[p]); //沿路将父节点设为根节点
}

合并

回顾我们前文提到的，并查集是以集合中的元素来代表整个集合，所以合并的操作只需要把其中一个集合的代表元素的根节点设为另一个集合的代表元素即可。

1
2
3
4
5
6
7
8
void unite(int x, int y)
{
    x = find(x);
    y = find(y); //返回各自根节点
    if(x == y) 
        return;
    fa[x] = y; //将其中一个元素的根节点设为另一个元素
}

但是我们会发现，在合并过程中，我们的并查集极有可能会变成一条链，即发生退化，这会是我们的复杂的大大增加，所以我们需要尽可能减缓它变长的时间，于是我们可以：

  • 记录每棵树(集合)的高度(深度)
  • 合并时，将小的一方合并至大的一方
1
2
3
4
5
6
7
8
9
10
11
12
13
void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y) 
        return;
    
    if(h[x] < h[y])
        fa[x] = y; //小的向大的合并
    else fa[y] = x;
    if(h[x] == h[y]) 
        h[x]++; //高度相同，随意合并，高度加一
}

由于我们新增了一个数组，所以再初始化中需要再添加一行：

1
2
3
4
5
6
7
8
void init(int n)
{
    for(int i = 0; i < n; i++)
    {
        fa[i] = i;
        h[i] = 0;
    }
}

并查集的复杂度

优化后的并查集效率非常高，对于每一个元素，进行一次操作的复杂度为O(a(n))O(a(n))，其中a(n)a(n)是阿克曼函数的反函数。这比O(logn)O(logn)还要快。