【数据结构】并查集详解

首先解释一下什么是并查集，来自百度百科：

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。

这段文字讲的很详细，其实我们可以通俗的将并查集理解成一种处理点集之间的连通关系的数据结构。

既然是数据结构，那么就应该有对应的图来描述。并查集由许多相连或者不相连的点组成，我们维护这些点的祖先（父节点的父节点的父节点........），当某个点没有父节点（父节点为自身）时我们就说这个点是祖先节点。

值得注意的是，并查集中所有操作都只和根有关。

并查集一般有以下四种操作：

创建一个并查集

我们用 pre[i] 表示节点 i 的父节点（前导点），初始化pre[i] = i;

const int maxn = 1e5 + 10;
int pre[maxn];
inline void init(int N)//N为节点个数
{
	for(int i = 1;i <= N; ++ i)pre[i] = i;//初始化每个节点的父节点为自身
}

初始化完成后我们的并查集长这样（是不是很像一片森林）：

至此，我们就创建了一个并查集，接下来我们来连接两个点。

在合并之前我们需要找到节点的祖先，我们用root函数来找到祖先（根）。

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

接下来我们只需要将两个节点的根连接即可，连接就是将根的父节点设为另一个根。

inline void Merge(int x,int y)
{
	pre[root(x)] = root(y);
}

为什么不可以直接将 x 的父节点设置为 y 呢？因为这样会导致 x 丢失原来的祖先，使数据失真。

这里我们假设 1 的祖先是 2 ，我们来连接 1 6 两个节点，连接后并查集长这样：

这个操作非常简单，只要两个点的祖先是同一个那么连通，否则不连通。

inline bool iscon(int x,int y)
{
	return root(x) == root(y);
}

连通块的个数 = 根的个数，所以直接枚举找父节点为自身的节点个数。

inline int rootNum(int N)
{
	int res = 0;
	for(int i = 1;i <= N; ++ i)if(pre[i] == i)res ++;
	return res;
}

希望对你有帮助。