038.并查集-上

前置知识：无

并查集 §

使用场景 §

• 一开始每个元素都拥有自己的集合，在自己的集合里只有这个元素自己
• find(i)：查找 i 所在集合的代表元素
  • 代表元素：代表 i 所在的集合
  • 在一个集合中的元素代表元素一定相同；代表元素不同的元素必定不在同一集合
• boolean isSameSet(a, b)：判断 a 和 b 在不在一个集合里
• void union(a, b)：将 a 所在集合所有元素与 b 所在集合所有元素合并成一个集合
• 各种操作单次调用的均摊时间复杂度为 $O(1)$
  • 哈希表、链表等结构都能实现以上方法的效果，但是它们的各个方法复杂度做不到都是 $O(1)$

原理图解 §

优化 §

1. 路径扁平化（find 方法里）：一定要做，查找时不用遍历太长的路径
2. 小挂大（union 方法里）：可以不做，原论文中是秩的概念，可以理解为粗略高度或者大小

并查集的小扩展 §

下节课 的题目重点展示

可以定制信息：并查集目前有多少个集合，以及给每个集合打上标签信息

时间复杂度的理解 §

作为如此简单、小巧的结构，感性理解单次调用的均摊时间复杂度为 $O(1)$ 即可，其实为 $\alpha (n)$（阿克曼函数）

当 $n=10^{80}$ （$10^{80}$：可探明宇宙原子量），$\alpha (n)$ 的返回值也不超过 6，那就可以认为是 $O(1)$

并查集的发明者 Bernard A. Galler 和 Michael J. Fischer，从 1964 年证明到 1989 年才证明完毕，建议记住即可，理解证明难度很大

备注 §

带权并查集的内容是大厂笔试面试冷门内容，会在【挺难】课程里讲述。

可持久化并查集、可撤销并查集，更是比较冷门的内容，备战比赛的同学自行学习，本系列课程不再安排讲述

题目1.并查集模版（牛客） §

测试链接 §

并查集的实现

思路 §

• 小挂大
• 借助 stack 进行扁平化

效率更好，代码编写较繁琐

答案 §

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXN = 1e6 + 1
)
 
var (
	n      int
	father = [MAXN]int{}
	size   = [MAXN]int{}
	stack  = [MAXN]int{}
)
 
// 初始化：一开始每个元素都拥有自己的集合，在自己的集合里只有这个元素自己
func build() {
	for i := 1; i <= n; i++ {
		father[i] = i
		size[i] = 1
	}
}
 
// i 号节点，往上一直找，找到代表节点返回
// 并对沿途节点进行扁平化（father 直接挂在代表节点上）
func find(i int) int {
	// 沿途收集了几个点
	cnt := 0
	for i != father[i] {
		stack[cnt] = i
		cnt++
		i = father[i]
	}
	// 沿途节点收集好了，i 已经跳到代表节点了
	// 对沿途节点进行扁平化
	for cnt > 0 {
		cnt--
		father[stack[cnt]] = i
	}
	return i
}
 
func isSameSet(a, b int) bool {
	return find(a) == find(b)
}
 
func union(a, b int) {
	af := find(a)
	bf := find(b)
	if af == bf {
		return
	}
    // 小挂大
	if size[af] < size[bf] {
		father[af] = bf
		size[bf] += size[af]
	} else {
		father[bf] = af
		size[af] += size[bf]
	}
}
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		m, _ := strconv.Atoi(in.Text())
		build()
		for op, a, b := "", 0, 0; m > 0; m-- {
			in.Scan()
			op = in.Text()
			in.Scan()
			a, _ = strconv.Atoi(in.Text())
			in.Scan()
			b, _ = strconv.Atoi(in.Text())
			switch op {
			case "1":
				if isSameSet(a, b) {
					fmt.Fprintln(out, "Yes")
				} else {
					fmt.Fprintln(out, "No")
				}
			case "2":
				union(a, b)
			}
		}
	}
	out.Flush()
}

题目2.并查集模版（洛谷） §

测试链接 §

P3367 【模板】并查集

思路 §

• 不考虑小挂大
• 递归进行扁平化

效率稍差（差不了多少），代码编写很简洁

答案 §

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXN = 10001
)
 
var (
	n      int
	father = [MAXN]int{}
)
 
// 初始化：一开始每个元素都拥有自己的集合，在自己的集合里只有这个元素自己
func build() {
	for i := 1; i <= n; i++ {
		father[i] = i
	}
}
 
// i 号节点，往上一直找，找到代表节点返回
// 并对沿途节点进行扁平化（father 直接挂在代表节点上）
func find(i int) int {
	if i != father[i] {
		father[i] = find(father[i])
	}
	return father[i]
}
 
func isSameSet(a, b int) bool {
	return find(a) == find(b)
}
 
func union(a, b int) {
	// 不管小挂大
	father[find(a)] = find(b)
}
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		m, _ := strconv.Atoi(in.Text())
		build()
		for op, a, b := "", 0, 0; m > 0; m-- {
			in.Scan()
			op = in.Text()
			in.Scan()
			a, _ = strconv.Atoi(in.Text())
			in.Scan()
			b, _ = strconv.Atoi(in.Text())
			switch op {
			case "1":
				union(a, b)
			case "2":
				if isSameSet(a, b) {
					fmt.Fprintln(out, "Y")
				} else {
					fmt.Fprintln(out, "N")
				}
			}
		}
	}
	out.Flush()
}

题目3.情侣牵手 §

题目描述 §

n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。

人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。

返回最少交换座位的次数，以便每对情侣可以并肩坐在一。 每次交换可选择任意两人，让他们站起来交换座位。

示例 1：

输入：row = [0,2,1,3]

输出：1

解释：只需要交换 row[1] 和 row[2] 的位置即可

示例 2：

输入：row = [3,2,0,1]

输出：0

解释：无需交换座位，所有的情侣都已经可以手牵手了

提示:

• 2n == row.length
• 2 <= n <= 30
• n 是偶数
• 0 <= row[i] < 2n
• row 中所有元素均无重复

测试链接 §

765.情侣牵手

思路 §

判断一个人是第几对情侣：i/2，比如：0 和 1 是第 0 对情侣，即：0/2=0，1/2=0

如果相邻的两个人不是情侣，就将这两个情侣对合并，最后要调整的次数就是合并了的情侣对的数量减一

比如：row = [0,2,1,3]

情侣对：{0}、{1}

• 0 是第 0 对情侣、2 是第 1 对情侣，将第 0 对情侣和第 1 对情侣合并：{0,1}
• 1 是第 0 对情侣、3 是第 1 对情侣，将第 0 对情侣和第 1 对情侣合并：{0,1}

要调整的次数：{0,1} 中两个元素 - 1 = 1

如果最终情侣对集合变成：{0,1,2,3}、{4,5}、{6}，那么要调整的次数 = (4-1) + (2-1) + (1-1) = (4+2+1) - 3，即：情侣对个数 - 集合个数

代码很简单，思路很难想！

答案 §

const (
	MAXN = 31
)
 
var (
	father   = [MAXN]int{}
	setCount int // 集合个数
)
 
func minSwapsCouples(row []int) int {
	n := len(row)
	build(n >> 1)
	for i := 0; i < n; i += 2 {
		union(row[i]>>1, row[i+1]>>1)
	}
	return n>>1 - setCount
}
 
func build(n int) {
	for i := 0; i < n; i++ {
		// 第 i 对情侣
		father[i] = i
	}
	setCount = n
}
 
func find(i int) int {
	if i != father[i] {
		father[i] = find(father[i])
	}
	return father[i]
}
 
func union(a, b int) {
	af := find(a)
	bf := find(b)
	if af == bf {
		return
	}
	father[af] = bf
	setCount--
}

复杂度 §

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

题目4.相似字符串组 §

题目描述 §

如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。

例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。

总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。

给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。请问 strs 中有多少个相似字符串组？

提示：

• 1 <= strs.length <= 300
• 1 <= strs[i].length <= 300
• strs[i] 只包含小写字母。
• strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。

测试链接 §

839.相似字符串组

答案 §

const (
	MAXN = 301
)
 
var (
	father   = [MAXN]int{}
	setCount int // 集合个数
)
 
func numSimilarGroups(strs []string) int {
	n := len(strs)
	m := len(strs[0])
	build(n)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if find(i) == find(j) {
				continue
			}
			diff := 0
			for k := 0; k < m && diff < 3; k++ {
				if strs[i][k] != strs[j][k] {
					diff++
				}
			}
			// 相似
			if diff == 0 || diff == 2 {
				union(i, j)
			}
		}
	}
	return setCount
}
 
func build(n int) {
	for i := 0; i < n; i++ {
		father[i] = i
	}
	setCount = n
}
 
func find(i int) int {
	if i != father[i] {
		father[i] = find(father[i])
	}
	return father[i]
}
 
func union(a, b int) {
	af := find(a)
	bf := find(b)
	if af == bf {
		return
	}
	father[af] = bf
	setCount--
}

复杂度 §

• 时间复杂度：$O(n^2\ast m)$
• 空间复杂度：$O(n)$

题目5.岛屿数量 §

题目描述 §

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

测试链接 §

200.岛屿数量

答案 §

const (
	MAXN = 301 * 301
)
 
var (
	father   = [MAXN]int{}
	setCount int
 
	n       int
	m       int
	theGrid [][]byte
)
 
func numIslands(grid [][]byte) int {
	n = len(grid)
	m = len(grid[0])
	theGrid = grid
	build()
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == '1' {
				// 左边
				if j > 0 && grid[i][j-1] == '1' {
					union(getIdx(i, j), getIdx(i, j-1))
				}
				// 上边
				if i > 0 && grid[i-1][j] == '1' {
					union(getIdx(i, j), getIdx(i-1, j))
				}
				// 右边和下边：之后会遍历到
			}
		}
	}
	return setCount
}
 
func build() {
	setCount = 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if theGrid[i][j] == '1' {
				idx := getIdx(i, j)
				father[idx] = idx
				setCount++
			}
		}
	}
}
 
func find(i int) int {
	if i != father[i] {
		father[i] = find(father[i])
	}
	return father[i]
}
 
func union(a, b int) {
	af := find(a)
	bf := find(b)
	if af == bf {
		return
	}
	father[af] = bf
	setCount--
}
 
// 一维并查集索引如何存储二维位置？
// 0 1 2
// 3 4 5
// 6 7 8
func getIdx(i, j int) int {
	return m*i + j
}

复杂度 §

并查集：

• 时间复杂度：$O(n\ast m)$
• 空间复杂度：$O(n\ast m)$

之后会讲 洪水填充的解法：

• 时间复杂度：$O(n\ast m)$
• 空间复杂度：$O(1)$

洪水填充和并查集解法的时间复杂度相同，但洪水填充常数时间更优