并查集

什么是并查集?

并查集是一种树型的数据结构，用来处理一些不交集的合并以及查询问题的。有union-find算法定义了两个用于对并查集寻找和合并的操作。即为find函数和union函数（一般我称之为merge函数）。并查集主要是快速对某些关系进行记录，选取一个节点作为一个组合的代表，从而实现快速分组，当然oj题中常涉及到的关系网问题也是一种分组问题，可以通过并查集来实现。

union-find函数的实现

首先我们来学习一下两个函数的用途：

• Find函数：确定元素属X于哪一个子集，这个确定的方法就是不断向上查找找到它的根节点Y（当然了这个根节点Y肯定是和X就同属于一个共同集合了并且这个集合就是以X为代表的），所以我们称这个集合为Y集合。
• Union函数（或者叫Merge函数）：顾名思义，肯定是用来将两个集合合并成为一个集合。

并查集分类思想

其实我们前面提到了，在并查集中，会选择一个节点Y作为一个集合的代表，那么对于任意一个元素X，如果它属于集合Y，那么通过Find(X)就会返还这个集合的代表根节点Y。因此虽然集合中的元素应该都是同级的，但是实际上在并查集中根节点代表元素会是根节点因此处于最高级。而Union函数若想将两个集合合并最简单的思想，就是将两个集合的代表元素放到一个集合建立关系，那么也就是集合A的代表元素A成为集合B的代表元素B的父节点（即将集合B并入到A集合中）或者也可以将集合B的代表元素成为集合A的父节点（即将集合A并入到B集合中）。如下图：

此时A,C,D在一个集合中，且A是集合的代表元素，所以A是根节点，他是C,D的父节点。B,E,F,G在一个集合中并且B是集合的代表元素，所以B是根节点，同时每一个节点一直向上查找最终都会找到B。所以我们就可以写出Find函数的伪代码了：

1
2
3
4
5
6
7

int Find(int x){
    //如果到达了根节点，那么就返还自身
	if(x.parent==x)
		return x;
    //如果不是根节点，那么就继续向上查找
	else return Find(x);
}

那么现在我们来尝试合并，其实就是将不同集合的代表元素即两个元素的根节点合并，其中一个根节点成为另一个根节点的父元素。因为传入的参数节点未必是根节点，所以我们首先需要用到Find函数来找到两个代表元素根节点，所以伪代码如下：

1
2
3
4

void Union(int x,int y){
    //Y的根节点成为X的根节点的父元素
	Find(x).parent=Find(y);
}

优化一：按秩合并

所以上面函数的功能是将x的集合并入y的集合，因此y的根节点仍会是新的合并集合的代表元素。比如我们现在要使用Union(C,F),那么最终树的结构如下：

那么最终F的集合的代表元素B会成为C的集合代表元素A的父节点，因此最终所有元素都会纳入B集合。因此Union函数会用到Find函数，同时Union函数的后一个参数是会成为根节点。

现在如果我们写的是Union(G,D)，那么最终树的结构会如下：

实际上从功能上来，这两个貌似没有什么区别，最终都是实现了两个集合的合并。但是我们对比一下上面两个结果图，发现第一种方法最终实现后树的深度不变还是3，但是对于第二种方法最终树的深度会变为4，如果每一次深度大的树总是合并到右子树，那么最终整体树会变得很不平衡，且深度很大。所以我们在合并时可以要求每一次都是深度小的子树合并到深度大的子树上，这样就不会影响合并后的树深度变大了。但是如果刚好两个树深度相同，那么就随意了，深度肯定是会加一的。因此Union函数伪代码优化为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void Union(int x,int y){
    //记录x的根节点
	int xRoot=Find(x);
	//记录y的根节点
    int yRoot=Find(y);
    //如果x集合深度更小，那么将x合并到y中即y是根节点
    if(xRoot.rank<yRoot.rank)
        xRoot.parent=yRoot;
    //如果y集合深度更小，那么将y合并到x中即x是根节点
    else if(xRoot.rank>yRoot.rank)
        yRoot.parent=xRoot;
    else
    //两个集合深度刚好相等
        xRoot.parent=yRoot;
    //合并以后集合y的深度增加一
    	yRoot.rank+=1;
}

又因为在并查集中我们一般称集合树的深度为秩，每次都是将深度小的合并到深度大的集合树中，也就是将秩小的树合并到秩大的树上，因此称为按秩（小）合并。

优化二：路径压缩

这是一种在执行查找时扁平化树结构的方法。关键点就是在路径上的每一个节点都直接连在根上，他们有同样的表示方法，都只需至多查找一次即可到达根节点。这样操作速度就会加快了同时树的深度一直会是2，即根节点以及许许多多的叶子节点。

Find函数的伪代码如下：

1
2
3
4
5
6
7
8
9

int Find(int x){
    //如果x不是根节点
    if(x.parent!=x)
        //那么继续Find向上查找，同时x的父节点更新为根节点
        x.parent=Find(x.parent);
    else
        //否则是根节点直接返还自身
        return x;
}

比如现在知道B是E的父节点，同时E是F和G的父节点，那么也就下图：

现在我们Find(E)后，会返还B，又因为此时B就是E的父节点，那么树结构不变，但是现在要Find(F)后，会一直向上查找到根节点B同时更新F直接连接根节点B，所以变成下图：

一定要注意Find函数是将查找路径上的所有节点都连接到根节点上，这是由于递归先执行内递归层，再返还执行外递归层导致的。比如现在知道了H是G的子节点，即如下图：

那么我们触发了Find(H)后会return Find(G)所以在Find(H)还没有返还根节点之前又触发了Find(G)，所以又会执行Find(G),因此G会连接到根节点。Find(G)执行完以后且Find(H)未return前的树结构图如下：

然后Find(H)执行完以后即return B以后也连接到了B上，因此树结构会变成：

因此这种Find函数保证了树的结构扁平化，永远保持秩为2，因此操作更快。同时由于Union函数中也有Find函数，因此Union后也会变成上图这样的深度为2的数。比如

此时我们触发Union(D,F)以后，最终结果会变成

因此我们现在知道了树与节点的Find和Union方法了。

用数组模拟并查集

但是我们知道在做oj题时不可能写一个树，所以一般是使用更简单的数组来模拟，我们只需要一个fa数组，来存储每一个节点的父节点键值即可。所以假设2的父节点是6，那么fa[2]=6。所以fa数组值相同的键值节点是同一个集合的。初始化时所有值都等于自身键值即可，所以也就初始化成了每一个数各是一个集合的情况，当两者建立关系时会出现相同的值。我们先给出板子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void initFa(int n){
    for(int i=1;i<=n;i++)
        fa[i]=i;
}

int Find(int x){int find(int x)
{
    //路径压缩的查找
    //寻找最深层祖先，同时压缩更新x的祖先为最深层祖先
    return (fa[x] == x ? x : fa[x] = find(fa[x]));
}

void merge(int x, int y)
{
    //x的最深层祖先的祖先更新为y，这样x和y就有关系了，同时y会成为更深层的根本祖先
    if (find(x) != find(y))
        fa[find(x)] = find(y);
}

比如现在有5个数1,2,3,4,5，那么初始化以后fa[1=1],fa[2]=2…fa[5]=5。如果现在合并1和2且是merge(1,2),那么就会出现fa[1]=2,fa[2]=2,fa[3]=3,fa[4]=4,fa[5]=5。假设现在由触发merge(5,1)，那么最终fa[1]=2,fa[2]=2,fa[3]=3,fa[4]=4,fa[5]=2。

并查集解决分组问题

实际上刚刚上面我们举例的1,2,3,4,5就是分组问题，最终实现的就是1,2,5同一组，3自己一组，4自己一组。类似的题还有给出10个树，根据不同的题意进行分组，最终判断有几个森林，实际上最终就是统计fa数组中有几种不同的数就是有几个森林。

并查集解决关系网问题

一般给出的关系网会规定如果a和b有关系，b和c有关系，那么a和c也会有关系，我们仔细思考一下，实际上就可以使用并查集来模拟，只要x,y都同属于同一个根节点就说明两个及节点x,y有关系，只是在并查集中各个节点并不是同级的，而会有父子节点的关系，但是这并不影响关系网的建立。