目录
- 前言
- 一、引例
- 二、结合引例写出并查集
- 1. 并查集维护一个数组
- 2. 并查集的 并 操作
- 3. 并查集的 查 操作
- 4. 基本并查集模板代码实现——第一版(有错误后面分析)
- 5. 一个错误
- 6. 基本并查集模板代码实现——第二版(解决错误)
- 7. 一点点解释,为什么无需在意谁是谁的爸爸
- 三、并查集的优化
- 1. 并查集优化原理
- 2. 基本并查集模板代码实现——第三版(优化)
- 四、例题
前言
并查集算法适用于处理一些不相交集合的合并及查询问题。对于这一类的问题使用并查集,不但节省了空间,而且大大缩短了运行时间。
基本的并查集很好写出一个模板,对于一些特殊的题目也能很好对并查集进行变形,接下来来看一下引例了解一下并查集
一、引例
男生寝室关系错综复杂,甚至一个四人寝室都能整出四个爸爸四个儿子。
有一天宿管阿姨想知道这个寝室楼里有多少个爸爸家族,但是宿管只知道哪两个人互称爸爸。
上图是宿管阿姨花了三天三夜整理的爸爸关系图,宿舍楼里总共有n个男生,所以她将每个男生编号0~(n-1)。刚开始人不多,所以阿姨想看0和6是不是一个家族的,只需要看这几个关系即可知道0和6是一个爸爸家族的
后来学生知道了,纷纷来宿管这儿查关系,想看看自己有多少个儿子,自己和隔壁班的学霸是不是爸爸关系。
这一下可给宿管忙坏了,有时候得追溯到十几个人才能确定两个人有爸爸关系,而且还会查错走不少弯路,于是阿姨花了一个晚上,硬生生把关系无向图给画出来了,这下子学生一看图就能知道自己在爸爸家族有多少儿子。
时间一长,学生跑来和宿管讲:“阿姨阿姨,我又有新儿子了,我是0,我儿子是7”,于是阿姨在图上简单地画一下,一个新关系图出来了
二、结合引例写出并查集
1. 并查集维护一个数组
说来你可能不信,以上就是并查集的思路了!下面我们回归正题,在上面例子中,我们涉及到了两个操作,一个是查找,一个是合并,这也是并查集名字的由来。
在这里我们新建一个数组arr,图示第一行为坐标i,第二行为数组元素的内容arr[i],数组坐标就是学生的编号,分别是0, 1, 2, …, n-1。arr[x]的值表示编号为x的同学的爸爸是谁。初始值表示自己就是自己的爸爸,所以arr[x]=x。
2. 并查集的 并 操作
接下来一个“父子关系”加入了,0说3是儿子,3说0是儿子,谁也争持不下,那就偷偷的规定右边是左边的爸爸,不告诉他们。(你可能会疑惑,为什么要这样规定,可以反过来吗?后面会做出解释,你姑且先放一边哈)
接下来循环往复,重复以上操作,依次将2与5,4与6合并
我们通过对数组元素的修改,得到了一个集合,我们可以用无向图来表示。按照0的爸爸是3,3的爸爸是4,4的爸爸是6等这样来把它们连起来
3. 并查集的 查 操作
我们要查找0和4是不是一个家族的,就需要查看0的祖先和4的祖先是同一个人吗?换句话说也就是只需要向上依次查询0的爸爸的爸爸的爸爸,查询4的爸爸的爸爸的爸爸,直到最后的爸爸的爸爸是他自己,就说明这个是爸爸家族里的祖先。下面给出图示说明
做出一点解释,对于第一步,因为数组arr对应的arr[x]=y,表示编号为x的人的爸爸是y,所以要想知道x的父亲,必须访问arr[x]即可知道
对于第二步,祖先一定满足arr[x]=x,即爸爸的爸爸是自己,所以只要不满足arr[x]=x的,一定x一定还有爷爷,这时候就要一直向上查询x的爷爷爷爷爷爷爷爷,直到第六步所示,arr[6]=6表示6是祖先!我们找到了!!
4. 基本并查集模板代码实现——第一版(有错误后面分析)
这样一来,我们简单地得到了第一版的并查集:
/**
* @author 太白
*/
public class UnionFind {
private int[] arr;
public UnionFind(int size) {
arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = i; // 初始化,每个人是自己的父亲,即每个人都是祖先
}
}
public int find(int son) {
int father = arr[son];
// 循环,直到爸爸的爸爸是自己为止
while (father != arr[father]) {
father = arr[father];
}
return father;
}
public void union(int son1, int son2) {
// 此处有错误,可以思考一下,下面我们举例说明为什么错了
arr[son1] = son2; // 合并,son1的爸爸是son2
}
}
5. 一个错误
我们给出一种情况,我们加了一个新关系,0的爸爸是2,来看看我们现在的代码是否能完成预期功能
完蛋!由于我们在union方法中只是进行arr[son1]=son2;
导致原先的祖爷爷6少了一个孙子0,孙子0归祖爷爷5去了,简直是背盟败约,跑到了别的爸爸家族里面去了!!!
没事,其实解决方法特别简单!别被这个小错误给乱了阵脚,这也是起初学该算法容易犯的错误,可以注意一下。
我们维护的是m个爸爸家族,所以如果我们将整个爸爸家族当做是一个人,另一个爸爸家族当做是另一个人,再让这两个巨大的人互认爸爸儿子即可。自然,我们肯定会让祖爷爷出面,去和另一个家族比拼,谁赢了就谁当爸爸。(当然无所谓谁当,后面会解释)
6. 基本并查集模板代码实现——第二版(解决错误)
现在,我们给出第二版,解决了上述的BUG,你会看到解决方式是如此的简单,代码也很好理解,找到双方的祖先,最后让son2的祖先当son1祖先的爸爸。
/**
* @author 太白
*/
public class UnionFind {
private int[] arr;
public UnionFind(int size) {
arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = i;
}
}
public int find(int son) {
int father = arr[son];
while (father != arr[father]) {
father = arr[father];
}
return father;
}
public void union(int son1, int son2) {
// 请相信我,只改动了这里,其他地方都没有修改过
int father1 = find(son1);
int father2 = find(son2);
// 注意中括号里面的son改成了father
arr[father1] = father2;
}
}
7. 一点点解释,为什么无需在意谁是谁的爸爸
在上面我们的代码中默认了都是son1的爸爸是son2,那我们可以让son2的爸爸是son1吗?答案是可以!
因为我们维护的是集合,只是确认一个集合里有谁即可。
从语义上讲:今天你是我爸爸,明天我是你爸爸,但是我们依然是一个爸爸家族里的一员,所以不需要在意谁是谁的爸爸。
从家族结构来讲:整个家族就是一个无向图,关系是双向的。0可以是3的爸爸,3也可以是0的爸爸,所以无需刻意要求,当然也可以在代码里反着写arr[father2]=father1
三、并查集的优化
1. 并查集优化原理
可以看到我们每次查询都得一个一个向上查,0的爸爸是3,3的爸爸是4,4的爸爸是6,6的爸爸是6…如果我们数据量大一点,一个宿舍楼上万人,那么我们每次查询最大可能得查上万次,这太花时间啦!那么我们能不能做出一点改进呢?诶你别说,还真有~
思路是这样的,毕竟我们每次都得查询x的祖先是谁,不关心x的爸爸是谁,x的爷爷是谁,那为什么不直接让arr[x]指向它的祖先编号y呢,在本例中我们为什么不让arr[0]=6, arr[3]=6, arr[4]=6呢?
所以我们在本例中,可以让0、3、4的爸爸直接认定为6即可。延续上一次的查找,我们再多一项功能就是再次遍历0的爸爸3、4,让3和4的爸爸设置为6
2. 基本并查集模板代码实现——第三版(优化)
代码实现也很简单,我们只需要在find方法中加个四五行即可
/**
* @author 太白
*/
public class UnionFind {
private int[] arr;
public UnionFind(int size) {
arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = i;
}
}
public int find(int son) {
int father = arr[son];
while (father != arr[father]) {
father = arr[father];
}
// 直到循环到祖先为止
while (father != arr[son]) {
// 保存当前son的爸爸
// 因为要更改son的爸爸,所以要有个备份
int next = arr[son];
// 将son的爸爸改成father
arr[son] = father;
// 找到下一个爸爸(用备份的爸爸赋值给son即可)
// 将son改成下一个爸爸,为下一个循环做准备
son = next;
}
return father;
}
public void union(int son1, int son2) {
int father1 = find(son1);
int father2 = find(son2);
arr[father1] = father2;
}
}
于是,我们的模板就算是做好了,我习惯在里面添加两个方法,一个是isFamily(int, int)
,另一个是getCategory()
,第一个可以检测两个人是不是同一个爸爸家族的成员,另外一个看看总共有多少个爸爸家族,这两个方法经常在题目中用到,也很好实现,所以后续我们会结合例题,看如何十分简单地运用该算法解决一些相对复杂的题目。
四、例题
未完待续…