1.并查集基础知识

  • 并查集是一种树形结构，每个元素都存储在树中的一个结点里
  • 不同的树代表不同的集合，以根结点为标识
  • 当两个结点的根结点相同，就称这两个结点属于同一个集合，他们拥有一个共同的祖先结点。
  • 当两个结点的根结点不同，就称这两个结点不属于同一个集合，即位于不同的树结构中。
  • 查询一个结点所属的集合(即该结点的根结点），称之为Find，即查操作
  • 把两个不同集合(即不同的树)，合并到一个集合中，称之为Union，即并操作

2.并查集建树思想

初始化每个元素都是一个集合，都是树中的根结点，不同的集合可以根据需要进行合并，并查集解决的问题就是判断某个元素属于哪个集合，以及把不同集合中的结点合并到同一个集合中（同一棵树中）

树的结构体设计如下：

1
2
3
4
struct Node{
    DataType val;
    Node* par;
}

初始化每个结点都是根节点，即par=NULL；当需要把两个结点所属的集合和并到一起时，只需要找到它们各自的根节点，并把其中一个根节点作为另一个根节点的孩子结点即可。

这样建立结构体的方式有点麻烦，一般会通过一个数组模拟树结构，具体的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int N=999
int fa[N];	//fa[i]=j 代表元素i的的根节点是j
void init()
{
    //初始化每个元素i的根节点都是自身
	for (int i = 1; i <= n; i++)fa[i] = i;
}
int find(int i)	//查找元素i的根结点
{
	if (i == fa[i])return i;//若i元素是根结点,直接返回
	return find(fa[i]);//否则,递归查找i的父亲结点fa[i]的根节点并返回;
}
void unite(int i, int j)
{
	int x = find(i);//找到i的根节点
	int y = find(j);//找到j的根节点
	if (x == y)return;//若根节点相同，则属于同一个集合，退出
	fa[x] = y;//否则令i的根节点x作为y的子结点，即把i,j所属的两个集合合并
}

3.路径压缩

1
2
3
4
5
6
7
void unite(int i, int j)
{
	int x = find(i);
	int y = find(j);
	if (x == y)return;
	fa[x] = y;//也可为fa[y]=x
}

注意上方的最后一行代码，考虑一种情况，当在合并元素a，b 的时候，

合并结果两种情况

  1. a->b
  2. b->a

在上方的思路中，这两种情况是随机的，假设是第1种

接着合并a->b，c，又会有两种情况

  1. a->b->c
  2. a->b，c->b

我们不妨假设还是第一种情况，得到a->b->c

这样在极端的情况下，n个元素可能得到a->b->c->d->e…….

最终一个树结构就可能退化成线性结构，并查集的优越之处就无法体现。

解决方法就是，当我们在执行find操作的时候，当i不是根结点时，需要递归查询其父亲结点fa[i]的根节点，最终查到根结点时递归会一层层退出，并返回根结点元素，此时可以把根节点元素赋值给fa[i]，这样一来，经过一轮查询后，每个结点都直接指向它的根节点，树的深度变成了2，只有一个根结点和若干直接子节点，这种优化称之为路径压缩。

路径压缩代码如下：

1
2
3
4
5
6
7
int find(int i)	
{
	if (i != fa[i])return i;//若i元素是根结点,直接返回
		fa[i]=find([fa])//否则则递归查找i的父亲结点fa[i]的根节点,;
    return fa[i];
}

4.并查集模板

最终的并查集模板如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<cstring>
const int N = 999;
int fa[N];
void init()
{
	memset(fa,-1,sizeof(fa));//初始化为-1表示自身为根结点，与for循环类似
}
int find(int i)
{
    return  fa[i] == -1? i: fa[i] = find(fa[i]);
	/*
	if (fa[i] == -1)//表示i是根节点，返回i
		return i;
	return fa[i] = find(fa[i]);
	*/
}
void unite(int u, int v)
{
	int r1 = find(u);
	int r2 = find(v);
	if (r1 == r2) return;
	fa[r2] = r1;
}

5.带权并查集

带权并查集：在对并查集进行路径压缩和合并操作时，除了fa[]数组保存元素之间的父子关系时，还存在一个(多个)数组rel[]，用来保存父子间的其它关系。

例如fa[i] = j, rel[i] = val，当val取不同值时代表父子间存在的不同关系，在此处代表，i的父节点是j，并且i与j的关系是val，把val理解为i与j的权值。

也就是说，权值代表着当前节点与父节点的某种关系（即使路径压缩了也是这样），通过权值，也可以将同一棵树下两个节点的关系表示出来。

带权并查集相对于初始并查集的区别是增加了对一个权值的维护，即除了fa[]外，增加一个数组ral[]维护儿子与父亲的关系，同样的数组ral也有find和unite两个操作，故现在要解决两个操作中的数组ral更新维护问题

因此，解决带权并查集，即解决数组rel[]的维护，需要考虑如下两个问题
1.已知儿子与父亲的关系，以及父亲与爷爷的关系，怎么求儿子与爷爷的关系
(即找到某个元素与该集合祖先的关系，find操作所要解决的)
2.已知儿子A与父亲A(祖先A)、儿子B与父亲B(祖先B),如何求父亲B和父亲A的关系
(即将两个元素的集合合并时，两个元素所属集合祖先之间的关系，unite操作要解决的)

带权并查集问题实质上是并查集的一种应用，在并查集的基础上增加了对父子结点间的关系维护，而维护过程中需要解决的两个问题(实际上是两种关系的转换)则需要根据具体情况，进行分析，最终得到关系的转换的表达式，实现对数组rel[]的维护，即不同元素间的权值关系维护。

推荐一道经典例题：poj 1182

附上我当时学习并查集写的题解