「图::连通」详解并查集并实现对应的功能 / 手撕数据结构（C++）

目录

概述

成员变量

创建销毁

根节点访问

路径压缩

启发式合并

复杂度

Code

---

概述

并查集，故名思议，能合并、能查询的集合,在图的连通性问题和许多算法优化上着广泛的使用。

这是一个什么数据结构呢？

一般来讲，并查集是由一系列集合组成的集合群。

其中，每个集合都有一个根节点，它的父亲仍是它自己，集合内其余的节点的父亲or祖宗均是这个节点，这样，一个根节点就领导了一个集合。而并查集支持这样的多个集合的访问以及合并操作。

每个集合都是一个树形结构，你可以认为并查集是一片森林。

听起来挺复杂度，但是其实很好实现。

成员变量

static constexpr int N = 1e5 + 5;一个无关紧要的常量，限制最大值。

int pre[N];父节点指针数组,pre[i]=j表示i的父亲是j，即二者处于同一集合。

int size[N];集合大小数组，只用每个集合的根节点上的size是有意义的，若i为根节点size[i]=x表示i所在的集合大小为x。

struct union_find_set {static constexpr int N = 1e5 + 5;int pre[N],size[N];...
};

创建销毁

在一开始，每个节点都单独成为一个集合，每个集合大小为1。

union_find_set(int n = N) {for (int i = 0; i < n; i++) {pre[i] = i;size[i] = 1;}
}

根节点访问

给定一个节点x，我们想访问他的根节点。

这一步可以递归实现：我们知道只有根节点的pre指向自己，所以如果pre[x]==x，我们就找到了根节点，否则沿着pre指针爬，传入下一级root。

int root(int x) {return pre[x] == x ? x : root(pre[x]);
}

路径压缩

沿着pre指针爬树的过程的时间复杂度是线性级别的，但是我们可以使用路径压缩：

当我们依次跳出递归时，额外将这一级x的pre指针更新为找到的根节点，这样，一棵树就由多层被压缩成了两层（根节点与叶子节点）。

int root(int x) {return pre[x] = (pre[x] == x ? x : root(pre[x]));
}

启发式合并

想合并两个集合，我们可以采用启发式合并，即按规模合并。

路径压缩并不是实时的，所以一般一个集合仍是多层的。在这种情况下，为了保持查询根节点的高效性，我们应该将小集合接在大集合之下（小集合中节点少，向上访问的总代价小，如果反过来，那么大集合中的大量节点想向上访问会极其不利）。

给出两个节点，将其所在的集合合并，我们先找出root，如果两个节点确实属于不同集合，我们将小集合接在大集合之下，这样就能保持根节点查询的效率。最后根节点的size。

void unite(int x, int y) {x = root(x), y = root(y);if (x == y)return;if (size[y] < size[x])std::swap(x, y);pre[x] = y;size[y] += size[x];
}

复杂度

时间复杂度：O(n) 使用路径压缩：O(1)~O(logn)

空间复杂度：O(n) 

Code

#include <algorithm>
#ifndef UNION_FIND_SET
#define UNION_FIND_SET
struct union_find_set {static constexpr int N = 1e5 + 5;int pre[N],size[N];union_find_set(int n) {for (int i = 0; i < n; i++) {pre[i] = i;size[i] = 1;}}int root(int x) {return pre[x] = (pre[x] == x ? x : root(pre[x]));}int get_size(int x) {return size[root(x)];}void unite(int x, int y) {x = root(x), y = root(y);if (x == y)return;if (size[y] < size[x])std::swap(x, y);pre[x] = y;size[y] += size[x];}
};
#endif