并查集 UnionFind

题解

图

并查集 UnionFind

背景

为了解决图的连通性问题，聪明的程序员引入一个非常有用的数据结构：并查集。

对于n个起初完全散落的点，不断将它们两两相连，在中间过程中，需要能迅速判断出两个节点是否已经相连，如果已经相连就不再连，没有则连接。

一个有意思的说明

可以类比为江湖建立各种门派的过程：

有个程序员写了个武侠游戏，设定了一个特别的江湖世界：江湖中共有n位大侠，按照程序员的习惯编号为0、1、2、……、n-1。一开始，所有人互相陌生。逐渐，人们开始认识， 2和5成为朋友，5和8成为朋友…… 有朋友关系的大侠开始组建帮派，如上面的2、5、8就成为一个帮派，虽然2和8还不认识，但因为中间人5的关系，他们三个成了一个帮派。

渐渐地，帮派越来越多，每个帮派的人数也越来越多。程序员设定了一些规则：每个人或者独行独往，或者最多加入一个门派，加入后不能退出，且仅仅认识帮派里自己的介绍人一个。那么要怎么迅速获知江湖里的两个人是不是属于同一个门派呢？

程序员可以为每个帮派指定一个帮主，这样可以用帮主来标识该帮，比如2、5、8组成的帮派选5为帮主，那么他们的帮派可称为“帮派5”。

起初，所有人独来独往，可以看成共n个帮派，每个帮派的帮主就是帮派里唯一的那一位。

有一天，2主动找5组建帮派，对于新帮派，2是自己的介绍人，2就作为帮主；5只知道自己加入了一个帮派，介绍人是2，但不知道帮主是谁，帮里还有谁。又有一天，5和8成了好友，5介绍8进了自己的帮派，8只认识帮派里的5。

类似地，1和4组建帮派，1成为帮主，后来1又认识并介绍7加入帮派，7只知道自己有组织了，介绍人是1，但不知道组织里还有哪些大侠。之后9认识了4，被4介绍进了帮派1。

只有程序员有上帝视角，知道每个帮派的帮主，每个人的介绍人。每个帮派的帮主知道自己是帮主，别人都只知道自己的介绍人。

有一天，大侠9遇到了大侠7，他们想知道对方是不是和自己同一个帮派的，是就把酒言欢，否就大打出手。9先打电话给自己的介绍人4，4打电话给自己的介绍人1，1说他们的帮派名叫做“帮派1”，4又回拨9告诉帮派的名字。7先打电话给自己的介绍人1，1说他们的帮派名叫做“帮派1”。9和7一对，发现大家都是帮派1的人，好，喝酒吃肉去。

大侠们都很健忘，每次都只记得自己的介绍人，忘了帮派名。

又有一天，9和5相遇了，他们分别打电话给自己唯一认识的人，最终分别知道了自己所在的帮派，原来9属于帮派1，5属于帮派2 9在帮派1，5在帮派2，两人一对，大打出手。

程序员于心不忍，打打杀杀不好玩，不如两个帮派合成一派吧，帮派1有1、4、7、9四个人，帮派2有2、5、8三个人，让帮派二并入帮派1吧。只需要让帮派2的帮主大侠2记录自己的介绍人为帮派1的帮主大侠1即可，这样帮派2的所有人并入了帮派1。

程序员虽然是这个世界的上帝，不过也有难题，比如怎么迅速判断两个人是否属于同一个组织呢？一层层找帮主，时间复杂度有点高。

好在这是个聪明的程序员，用数组模拟了这个世界，且想了些办法把帮派合并和查找某个人的帮派这两个操作好好优化了下：

实现

type UnionFind []int   
// 创建江湖世界
func NewUnionFind(n int) UnionFind {
	unionFind := make([]int, n)
	for i := range unionFind {
		unionFind[i] = i // 起初，每个人是自己的介绍人，也是自己的帮主
	}
	return unionFind
}   
// x和y所在的两个帮派合并
func (uf UnionFind) Union(x, y int) {
    rootX, rootY := uf.Find(x), uf.Find(y) // 先找到各自的帮主
    // 两个帮派合并，rootX罢免自己的帮主之位，加入帮派rootY，介绍人成为rootY
    // （随便，反过来也可以。更好的做法是按秩合并，选组织层级多或人多的帮派帮主做合并后帮派的帮主，进一步减少整个Union、Find操作的复杂度）
    uf[rootX] = rootY   
}   
// 寻找x的帮主
func (uf UnionFind) Find(x int) int {
	for uf[x] != x { // x的介绍人不是x自己，说明x不是帮主
		x = uf[x] // 一直向上找介绍人
	}
	return x // 自己的介绍人就是自己，这是帮主
}   

// 一个简单有效的优化：路径压缩
// 寻找x的帮主
func (uf UnionFind) Find(x int) int {
	for uf[x] != x { // x的介绍人不是x自己，说明x不是帮主
        // 找x介绍人的介绍人y，同时修改x的介绍人为y，这样组织才足够扁平化，后边再找帮主打电话的次数要少一些
		x, uf[x] = uf[x], uf[uf[x]]
	}
	return x // 自己的介绍人就是自己，这是帮主
}

并查集用数组来表示一张图，类似堆用数组表示一棵树，另外数组的索引和值有了关联（直观的做法是用哈希表，但尝试写写会发现并不如数组这样简洁），非常精妙高效。不得不说，程序员真是太聪明了。

Find 函数还可以写成递归版本：

// 寻找x的帮主
func (uf UnionFind) Find(x int) int {
	if uf[x] != x { // x的介绍人不是x自己，说明x不是帮主
        uf[x] = uf.Find(uf[x]) // 递归地，让 x 的介绍人是本帮帮主
	}
	return uf[x]
}

这个写法的效果是否和迭代写法一样呢？实际并不完全一样，可以画个图看看。这种写法的会导致从 x 到帮主这一路的大侠直接将帮主作为介绍人，整个组织被压得更扁，而迭代的方法并没有这么大的压缩力。另外在有些问题中，用递归版更利于编码，比如本文最后提到的问题：除法求值。

实际并查集就是一片森林（或者叫图），上边说帮派就是树，掌门就是树的根节点，每位大侠是一个节点，介绍人就是父节点。

并查集一般用数组实现，这样代码更简介，效率更高一些。

为了降低复杂度，并查集边查找边修改，这是其一大特色。

如果只做了路径压缩，没有做按秩合并，查找、合并复杂度会是 O(logN)，其中 N 是节点总数；路径压缩和按秩合并都做的话，平均复杂度会非常小，接近常数级。

实际中往往只需要做其中一个优化即可。

应用

值得一提的是，并查集还可以附加权值信息，来解决一些问题

除法求值

990. 等式方程的可满足性冗余连接