LeetCode Go · 并查集（2）

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

1101. 彼此熟识的最早时间 🔒

中等2 种解法

标签：并查集、数组、排序

题目、示例与约束

在一个社交圈子当中，有 n 个人。每个人都有一个从 0 到 n - 1 的唯一编号。我们有一份日志列表 logs，其中 logs[i] = [timestamp_i, x_i, y_i] 表示 x_i 和 y_i 将在同一时间 timestamp_i成为朋友。

友谊是相互的。也就是说，如果 a 和 b 是朋友，那么 b 和 a 也是朋友。同样，如果 a 和 b 是朋友，或者 a 是 b 朋友的朋友，那么 a 和 b 认识。

返回圈子里所有人之间都认识的最早时间。如果找不到最早时间，就返回 -1 。

示例 1：

输入：logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], N = 6
输出：20190301
解释：
第一次结交发生在 timestamp = 20190101，0 和 1 成为好友，社交朋友圈如下 [0,1], [2], [3], [4], [5]。
第二次结交发生在 timestamp = 20190104，3 和 4 成为好友，社交朋友圈如下 [0,1], [2], [3,4], [5].
第三次结交发生在 timestamp = 20190107，2 和 3 成为好友，社交朋友圈如下 [0,1], [2,3,4], [5].
第四次结交发生在 timestamp = 20190211，1 和 5 成为好友，社交朋友圈如下 [0,1,5], [2,3,4].
第五次结交发生在 timestamp = 20190224，2 和 4 已经是好友了。
第六次结交发生在 timestamp = 20190301，0 和 3 成为好友，大家都互相熟识了。

示例 2:

输入: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
输出: 3

提示：

2 <= n <= 100
1 <= logs.length <= 10⁴
logs[i].length == 3
0 <= timestamp_i <= 10⁹
0 <= x_i, y_i <= n - 1
x_i != y_i
timestamp_i 中的所有时间戳均不同
所有的对 (xi, yi) 在输入中最多出现一次

方法一：排序 + 并查集 · Go 实现

思考

问题等价于求最早时刻使 $n$ 人落在同一连通块。日志按时间乱序给出，因此须先按时间戳排序再依次处理。

每次结交若两人尚属不同集合，则用并查集合并并把连通块计数减一；查找与合并均可摊到近常数。计数减至 $1$ 时全体已互通，返回该条日志的时间；若扫完仍多于一块则返回 $- 1$ 。

我们将所有的日志按照时间戳从小到大排序，然后遍历排序后的日志，利用并查集判断当前日志中的两个人是否已经是朋友，如果不是朋友，则将两个人合并成一个朋友圈，直到所有人都在一个朋友圈中，返回当前日志的时间戳。

如果遍历完所有日志，还没有所有人都在一个朋友圈中，则返回 $- 1$ 。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为日志的数量。

func earliestAcq(logs [][]int, n int) int {
	sort.Slice(logs, func(i, j int) bool { return logs[i][0] < logs[j][0] })
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, log := range logs {
		t, x, y := log[0], log[1], log[2]
		if find(x) == find(y) {
			continue
		}
		p[find(x)] = find(y)
		n--
		if n == 1 {
			return t
		}
	}
	return -1
}

方法二 · Go 实现

思考

方法一将路径压缩写在主循环里，未按集合大小合并。方法二抽出带路径压缩与按大小合并的 UnionFind，union 仅在真正合并时返回真，主过程只维护连通块个数。判定「全体成为朋友」的时机与方法一相同，树高更受控。

type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func earliestAcq(logs [][]int, n int) int {
	sort.Slice(logs, func(i, j int) bool { return logs[i][0] < logs[j][0] })
	uf := newUnionFind(n)
	for _, log := range logs {
		t, x, y := log[0], log[1], log[2]
		if uf.union(x, y) {
			n--
			if n == 1 {
				return t
			}
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

1102. 得分最高的路径 🔒

中等2 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、二分查找、矩阵、Dijkstra 算法、堆（优先队列）

题目、示例与约束

给定一个 m x n 的整数矩阵 grid，返回从 (0,0) 开始到 (m - 1, n - 1) 在四个基本方向上移动的路径的最大分数。

一条路径的分数是该路径上的最小值。

例如，路径 8 → 4 → 5 → 9 的得分为 4 。

示例 1：

输入：grid = [[5,4,5],[1,2,6],[7,4,6]]
输出：4
解释：得分最高的路径用黄色突出显示。

示例 2：

输入：grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]]
输出：2

示例 3：

输入：grid = [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]
输出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 100
0 <= grid[i][j] <= 10⁹

方法一：排序 + 并查集 · Go 实现

思考

路径得分是路径上的最小格子值，要求从左上到右下最大化该值。枚举全部路径不可行。

将格子按值从大到小加入图中，并与已经加入的四邻用并查集合并。当前加入的值即「目前允许的最低分」；一旦起点与终点落入同一连通块，更小的格子尚未出现，无法再提高路径最小值，该值即为答案。

我们先将矩阵的每个元素构建一个三元组 $(v, i, j)$ ，其中 $v$ 表示元素值，而 $i$ 和 $j$ 分别表示元素在矩阵中的行和列。然后对这些三元组按照元素值从大到小进行排序，存放在列表 $q$ 中。

接下来，我们按顺序从 $q$ 中取出三元组，将其对应的元素值作为路径的分数，并且将该位置标记为已访问。然后我们检查该位置的上下左右四个相邻位置，如果某个相邻位置已经被访问过，那么我们就将该位置与当前位置进行合并。如果发现位置 $(0, 0)$ 和位置 $(m - 1, n - 1)$ 已经被合并，那么我们就可以直接返回当前路径的分数，即为答案。

时间复杂度 $O (m \times n \times (\log (m \times n) + α (m \times n)))$ ，其中 $m$ 和 $n$ 分别为矩阵的行数和列数。

func maximumMinimumPath(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	p := make([]int, m*n)
	vis := make([][]bool, m)
	q := [][3]int{}
	for i, row := range grid {
		vis[i] = make([]bool, n)
		for j, v := range row {
			p[i*n+j] = i*n + j
			q = append(q, [3]int{v, i, j})
		}
	}
	sort.Slice(q, func(i, j int) bool { return q[i][0] > q[j][0] })
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	dirs := [5]int{-1, 0, 1, 0, -1}
	for _, t := range q {
		v, i, j := t[0], t[1], t[2]
		ans = v
		vis[i][j] = true
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if 0 <= x && x < m && 0 <= y && y < n && vis[x][y] {
				p[find(x*n+y)] = find(i*n + j)
			}
		}
		if find(0) == find(m*n-1) {
			break
		}
	}
	return
}

方法二 · Go 实现

思考

方法一用数组直接做路径压缩。方法二改为带按大小合并的并查集类，合并与查询接口更规整，最坏链长更短。仍按格子值从大到小加入，并在起点与终点连通时停止。

type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) {
	pa, pb := uf.find(a), uf.find(b)
	if pa != pb {
		if uf.size[pa] > uf.size[pb] {
			uf.p[pb] = pa
			uf.size[pa] += uf.size[pb]
		} else {
			uf.p[pa] = pb
			uf.size[pb] += uf.size[pa]
		}
	}
}

func maximumMinimumPath(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	uf := newUnionFind(m * n)
	vis := make([][]bool, m)
	q := [][3]int{}
	for i, row := range grid {
		vis[i] = make([]bool, n)
		for j, v := range row {
			q = append(q, [3]int{v, i, j})
		}
	}
	sort.Slice(q, func(i, j int) bool { return q[i][0] > q[j][0] })
	dirs := [5]int{-1, 0, 1, 0, -1}
	for _, t := range q {
		v, i, j := t[0], t[1], t[2]
		ans = v
		vis[i][j] = true
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if 0 <= x && x < m && 0 <= y && y < n && vis[x][y] {
				uf.union(x*n+y, i*n+j)
			}
		}
		if uf.find(0) == uf.find(m*n-1) {
			break
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1135. 最低成本连通所有城市 🔒

中等1 种解法

标签：并查集、图、最小生成树、堆（优先队列）

题目、示例与约束

想象一下你是个城市基建规划者，地图上有 n 座城市，它们按以 1 到 n 的次序编号。

给你整数 n 和一个数组 conections，其中 connections[i] = [x_i, y_i, cost_i] 表示将城市 x_i 和城市 y_i 连接所要的cost_i（连接是双向的）。

返回连接所有城市的最低成本，每对城市之间至少有一条路径。如果无法连接所有 n 个城市，返回 -1

该 最小成本 应该是所用全部连接成本的总和。

示例 1：

输入：n = 3, conections = [[1,2,5],[1,3,6],[2,3,1]]
输出：6
解释：选出任意 2 条边都可以连接所有城市，我们从中选取成本最小的 2 条。

示例 2：

输入：n = 4, conections = [[1,2,3],[3,4,4]]
输出：-1
解释：即使连通所有的边，也无法连接所有城市。

提示：

1 <= n <= 10⁴
1 <= connections.length <= 10⁴
connections[i].length == 3
1 <= x_i, y_i <= n
x_i != y_i
0 <= cost_i <= 10⁵

方法一：Kruskal 算法 · Go 实现

思考

要以最小总造价连通 $n$ 座城，即求最小生成树。边按造价排序后，用并查集只合并尚不连通的端点并累加费用；连通块减至 $1$ 时已是一棵树。若边用尽仍多于一块，图不连通，返回 $- 1$ 。

Kruskal 算法是一种贪心算法，用于计算最小生成树。

Kruskal 算法的基本思想是，每次从边集中选择一条最小的边，如果这条边连接的两个顶点不在同一个连通分量中，则将这条边加入到最小生成树中，否则舍弃这条边。

对于本题，我们可以将边按照连通成本从小到大排序，用并查集维护连通分量，每次选择一条最小的边，如果这条边连接的两个顶点不在同一个连通分量中，则合并这两个顶点，然后累加连通成本。如果出现连通份量为 $1$ 的情况，则说明所有顶点都连通了，返回累加的连通成本，否则返回 $- 1$ 。

时间复杂度 $O (m \times \log m)$ ，空间复杂度 $O (n)$ 。其中 $m$ 和 $n$ 分别为边数和顶点数。

func minimumCost(n int, connections [][]int) (ans int) {
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	sort.Slice(connections, func(i, j int) bool { return connections[i][2] < connections[j][2] })
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, e := range connections {
		x, y, cost := e[0]-1, e[1]-1, e[2]
		if find(x) == find(y) {
			continue
		}
		p[find(x)] = find(y)
		ans += cost
		n--
		if n == 1 {
			return
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

1168. 水资源分配优化 🔒

困难2 种解法

标签：并查集、图、Kruskal 算法、最小生成树、Prim 算法、堆（优先队列）、Boruvka 算法

题目、示例与约束

村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。

对于每个房子 i，我们有两种可选的供水方案：一种是直接在房子内建造水井，成本为 wells[i - 1] （注意 -1 ，因为 索引从0开始 ）；另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，其中每个 pipes[j] = [house1_j, house2_j, cost_j] 代表用管道将 house1_j 和 house2_j连接在一起的成本。连接是双向的。

请返回 为所有房子都供水的最低总成本 。

示例 1：

输入：n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
输出：3
解释： 
上图展示了铺设管道连接房屋的成本。
最好的策略是在第一个房子里建造水井（成本为 1），然后将其他房子铺设管道连起来（成本为 2），所以总成本为 3。

示例 2：

输入：n = 2, wells = [1,1], pipes = [[1,2,1]]
输出：2
解释：我们可以用以下三种方法中的一种来提供低成本的水:
选项1:
在1号房子里面建一口井，成本为1
在房子2内建造井，成本为1
总成本是2。
选项2:
在1号房子里面建一口井，成本为1
-花费1连接房子2和房子1。
总成本是2。
选项3:
在房子2内建造井，成本为1
-花费1连接房子1和房子2。
总成本是2。
注意，我们可以用cost 1或cost 2连接房子1和房子2，但我们总是选择最便宜的选项。

提示：

2 <= n <= 10⁴
wells.length == n
0 <= wells[i] <= 10⁵
1 <= pipes.length <= 10⁴
pipes[j].length == 3
1 <= house1_j, house2_j <= n
0 <= cost_j <= 10⁵
house1_j != house2_j

方法一：Kruskal 算法（最小生成树） · Go 实现

思考

每座房屋可自建井或经管道连到已有水源。引入虚点 $0$ ，建井视为 $0$ 到该房屋的边，问题化为 $n + 1$ 个点的最小生成树。边按费用排序后用并查集合并，连通块从 $n$ 减到 $0$ （虚点与 $n$ 座房屋已全连通）即得最小费用。

我们假设有一个水井编号为 $0$ ，那么我们可以将每个房子与水井 $0$ 之间的连通性看作是一条边，每条边的权值为该房子建造水井的成本。同时，我们将每个房子之间的连通性也看作是一条边，每条边的权值为铺设管道的成本。这样一来，我们就可以将本题转化成求一张无向图的最小生成树的问题。

我们可以使用 Kruskal 算法求出无向图的最小生成树。我们先把水井 $0$ 与房子之间的一条边加入 $p i p e s$ 数组中，然后将 $p i p e s$ 数组按照边权值从小到大排序。随后，我们遍历每一条边，如果这条边连接了不同的连通分量，我们就选用这条边，并将对应连通分量合并。如果当前的连通分量恰好为 $1$ ，那么我们就找到了最小生成树，此时的答案即为当前边权值，我们将其返回即可。

时间复杂度 $O ((m + n) \times \log (m + n))$ ，空间复杂度 $O (m + n)$ 。其中 $m$ 和 $n$ 分别是 $p i p e s$ 数组和 $w e l l s$ 数组的长度。

func minCostToSupplyWater(n int, wells []int, pipes [][]int) (ans int) {
	for i, w := range wells {
		pipes = append(pipes, []int{0, i + 1, w})
	}
	sort.Slice(pipes, func(i, j int) bool { return pipes[i][2] < pipes[j][2] })
	p := make([]int, n+1)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}

	for _, x := range pipes {
		pa, pb := find(x[0]), find(x[1])
		if pa == pb {
			continue
		}
		p[pa] = pb
		ans += x[2]
		n--
		if n == 0 {
			break
		}
	}
	return
}

方法二 · Go 实现

思考

方法一将并查集内联。方法二抽出按大小合并的 UnionFind，union 回报是否真正合并，主循环只累加费用并计数。构图与 Kruskal 顺序不变。

type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func minCostToSupplyWater(n int, wells []int, pipes [][]int) (ans int) {
	for i, w := range wells {
		pipes = append(pipes, []int{0, i + 1, w})
	}
	sort.Slice(pipes, func(i, j int) bool { return pipes[i][2] < pipes[j][2] })
	uf := newUnionFind(n + 1)
	for _, x := range pipes {
		if uf.union(x[0], x[1]) {
			ans += x[2]
			n--
			if n == 0 {
				break
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1202. 交换字符串中的元素

中等1 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、哈希表、字符串、排序

题目、示例与约束

给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。

你可以 任意多次交换 在 pairs 中任意一对索引处的字符。

返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。

示例 1:

输入：s = "dcab", pairs = [[0,3],[1,2]]
输出："bacd"
解释： 
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"

示例 2：

输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
输出："abcd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[0] 和 s[2], s = "acbd"
交换 s[1] 和 s[2], s = "abcd"

示例 3：

输入：s = "cba", pairs = [[0,1],[1,2]]
输出："abc"
解释：
交换 s[0] 和 s[1], s = "bca"
交换 s[1] 和 s[2], s = "bac"
交换 s[0] 和 s[1], s = "abc"

提示：

1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s 中只含有小写英文字母

方法一：并查集 · Go 实现

思考

若对每次交换都尝试所有排列， $n$ 与 $p a i r s$ 均可达 $10^{5}$ ，搜索空间过大。

交换关系具有传递性：可交换的下标构成若干连通分量，分量内字符可任意重排。字典序最小串即在每个分量内把字符按升序填回原下标。

并查集维护下标连通性后，按根收集字符并逆序排序，再按位置依次弹出最小字符写回。并查集给出分量，排序给出该分量的最优填充顺序。

我们注意到，索引对具有传递性，即如果 $a$ 与 $b$ 可交换，而 $b$ 与 $c$ 可交换，那么 $a$ 与 $c$ 也可交换。因此，我们可以考虑使用并查集维护这些索引对的连通性，将属于同一个连通分量的字符按照字典序排序。

最后，遍历字符串，对于当前位置的字符，我们将其替换为该连通分量中最小的字符，然后从该连通分量中取出该字符，继续遍历字符串即可。

时间复杂度 $O (n \times \log n + m \times α (m))$ ，空间复杂度 $O (n)$ 。其中 $n$ 和 $m$ 分别为字符串的长度和索引对的数量，而 $α$ 为阿克曼函数的反函数。

func smallestStringWithSwaps(s string, pairs [][]int) string {
	n := len(s)
	p := make([]int, n)
	d := make([][]byte, n)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, pair := range pairs {
		a, b := pair[0], pair[1]
		p[find(a)] = find(b)
	}
	cs := []byte(s)
	for i, c := range cs {
		j := find(i)
		d[j] = append(d[j], c)
	}
	for i := range d {
		sort.Slice(d[i], func(a, b int) bool { return d[i][a] > d[i][b] })
	}
	for i := range cs {
		j := find(i)
		cs[i] = d[j][len(d[j])-1]
		d[j] = d[j][:len(d[j])-1]
	}
	return string(cs)
}

力扣原题 · Doocs 题解来源

1254. 统计封闭岛屿的数目

中等2 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵

题目、示例与约束

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。

请返回 封闭岛屿 的数目。

示例 1：

输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。

示例 2：

输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出：1

示例 3：

输入：grid = [[1,1,1,1,1,1,1],
             [1,0,0,0,0,0,1],
             [1,0,1,1,1,0,1],
             [1,0,1,0,1,0,1],
             [1,0,1,1,1,0,1],
             [1,0,0,0,0,0,1],
             [1,1,1,1,1,1,1]]
输出：2

提示：

1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1

方法一：DFS · Go 实现

思考

封闭岛是不碰边界的陆地连通块。 $m, n \leq 100$ ，洪水填充即可。从每块未访陆地 DFS，途中把格子改成水以免重复；若整块都在内部则计数加一。

返回值用与运算汇合「当前格不在边界」与所有邻居的结果。现场修改兼作访问标记。

遍历矩阵，对于每个陆地，我们进行深度优先搜索，找到与其相连的所有陆地，然后判断是否存在边界上的陆地，如果存在，则不是封闭岛屿，否则是封闭岛屿，答案加一。

最后返回答案即可。

时间复杂度 $O (m \times n)$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

func closedIsland(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	dirs := [5]int{-1, 0, 1, 0, -1}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		res := 1
		if i == 0 || i == m-1 || j == 0 || j == n-1 {
			res = 0
		}
		grid[i][j] = 1
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0 {
				res &= dfs(x, y)
			}
		}
		return res
	}
	for i, row := range grid {
		for j, v := range row {
			if v == 0 {
				ans += dfs(i, j)
			}
		}
	}
	return
}

方法二：并查集 · Go 实现

思考

DFS 依赖递归栈与现场改图。并查集把相邻陆地连成块，边界格子再与虚拟节点相连；统计根等于自身且未连到虚拟点的陆地即可。迭代合并避免递归，语义仍是「不与边界连通的陆地块」。

我们可以用并查集维护每一块连通的陆地。

遍历矩阵，如果当前位置是在边界上，我们将其与虚拟节点 $m \times n$ 连接。如果当前位置是陆地，我们将其与下方和右方的陆地连接。

接着，我们再次遍历矩阵，对于每一块陆地，如果其根节点就是本身，那么答案加一。

最后返回答案即可。

时间复杂度 $O (m \times n \times α (m \times n))$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) {
	pa, pb := uf.find(a), uf.find(b)
	if pa != pb {
		if uf.size[pa] > uf.size[pb] {
			uf.p[pb] = pa
			uf.size[pa] += uf.size[pb]
		} else {
			uf.p[pa] = pb
			uf.size[pb] += uf.size[pa]
		}
	}
}

func closedIsland(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	uf := newUnionFind(m*n + 1)
	for i, row := range grid {
		for j, v := range row {
			if i == 0 || i == m-1 || j == 0 || j == n-1 {
				uf.union(i*n+j, m*n)
			}
			if v == 0 {
				if i+1 < m && grid[i+1][j] == 0 {
					uf.union(i*n+j, (i+1)*n+j)
				}
				if j+1 < n && grid[i][j+1] == 0 {
					uf.union(i*n+j, i*n+j+1)
				}
			}
		}
	}
	for i, row := range grid {
		for j, v := range row {
			if v == 0 && uf.find(i*n+j) == i*n+j {
				ans++
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1258. 近义词句子 🔒

中等1 种解法

标签：并查集、数组、哈希表、字符串、回溯

题目、示例与约束

给你一个近义词表 synonyms 和一个句子 text ， synonyms 表中是一些近义词对，你可以将句子 text 中每个单词用它的近义词来替换。

请你找出所有用近义词替换后的句子，按 字典序排序 后返回。

示例 1：

输入：
synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]],
text = "I am happy today but was sad yesterday"
输出：
["I am cheerful today but was sad yesterday",
"I am cheerful today but was sorrow yesterday",
"I am happy today but was sad yesterday",
"I am happy today but was sorrow yesterday",
"I am joy today but was sad yesterday",
"I am joy today but was sorrow yesterday"]

提示：

0 <= synonyms.length <= 10
synonyms[i].length == 2
synonyms[0] != synonyms[1]
所有单词仅包含英文字母，且长度最多为 10 。
text 最多包含 10 个单词，且单词间用单个空格分隔开。

方法一：并查集 + DFS · Go 实现

思考

近义词可传递，同义类是连通分量。单词与近义词均很少，先用并查集合并，再按根收集并按字典序排好。

生成句子时对每个词位：不在任何类中则原样留下，否则枚举该类所有词继续 DFS。连通分量给出可替换集合，DFS 按位置展开笛卡尔积。

我们可以发现，题目中的近义词是可以传递的，即如果 a 和 b 是近义词，b 和 c 是近义词，那么 a 和 c 也是近义词。因此，我们可以用并查集找出近义词的连通分量，每个连通分量中的单词都是近义词，并且按字典序从小到大排列。

接下来，我们将字符串 text 按空格分割成单词数组 sentence，对于每个单词 sentence[i]，如果它是近义词，那么我们就将它替换成连通分量中的所有单词，否则不替换。这样，我们就可以得到所有的句子。这可以通过 DFS 搜索实现。

我们设计一个函数 $d f s (i)$ ，表示从 sentence 的第 $i$ 个单词开始，将其替换成连通分量中的所有单词，然后递归地处理后面的单词。

如果 $i$ 大于等于 sentence 的长度，那么说明我们已经处理完了所有的单词，此时将当前的句子加入答案数组中。否则，如果 sentence[i] 不是近义词，那么我们不替换它，直接将它加入当前的句子中，然后递归地处理后面的单词。否则，我们将 sentence[i] 替换成连通分量中的所有单词，同样递归地处理后面的单词。

最后，返回答案数组即可。

时间复杂度 $O (n^{2})$ ，空间复杂度 $O (n)$ 。其中 $n$ 是单词的数量。

type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) {
	pa, pb := uf.find(a), uf.find(b)
	if pa != pb {
		if uf.size[pa] > uf.size[pb] {
			uf.p[pb] = pa
			uf.size[pa] += uf.size[pb]
		} else {
			uf.p[pa] = pb
			uf.size[pb] += uf.size[pa]
		}
	}
}

func generateSentences(synonyms [][]string, text string) (ans []string) {
	ss := map[string]bool{}
	for _, pairs := range synonyms {
		ss[pairs[0]] = true
		ss[pairs[1]] = true
	}
	words := []string{}
	for w := range ss {
		words = append(words, w)
	}
	d := map[string]int{}
	for i, w := range words {
		d[w] = i
	}
	uf := newUnionFind(len(words))
	for _, pairs := range synonyms {
		uf.union(d[pairs[0]], d[pairs[1]])
	}
	g := make([][]int, len(words))
	for i := range g {
		g[uf.find(i)] = append(g[uf.find(i)], i)
	}
	for i := range g {
		sort.Slice(g[i], func(a, b int) bool { return words[g[i][a]] < words[g[i][b]] })
	}
	t := []string{}
	sentences := strings.Split(text, " ")
	var dfs func(int)
	dfs = func(i int) {
		if i >= len(sentences) {
			ans = append(ans, strings.Join(t, " "))
			return
		}
		if _, ok := ss[sentences[i]]; !ok {
			t = append(t, sentences[i])
			dfs(i + 1)
			t = t[:len(t)-1]
			return
		} else {
			for _, j := range g[uf.find(d[sentences[i]])] {
				t = append(t, words[j])
				dfs(i + 1)
				t = t[:len(t)-1]
			}
		}
	}
	dfs(0)
	return
}

力扣原题 · Doocs 题解来源

1267. 统计参与通信的服务器

中等1 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、计数、矩阵

题目、示例与约束

这里有一幅服务器分布图，服务器的位置标识在 m * n 的整数矩阵网格 grid 中，1 表示单元格上有服务器，0 表示没有。

如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。

请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。

示例 1：

输入：grid = [[1,0],[0,1]]
输出：0
解释：没有一台服务器能与其他服务器进行通信。

示例 2：

输入：grid = [[1,0],[1,1]]
输出：3
解释：所有这些服务器都至少可以与一台别的服务器进行通信。

示例 3：

输入：grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
输出：4
解释：第一行的两台服务器互相通信，第三列的两台服务器互相通信，但右下角的服务器无法与其他服务器通信。

提示：

m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 0 or 1

方法一：计数 · Go 实现

思考

能通信当且仅当同行或同列还有另一台服务器。 $m, n \leq 250$ ，先统计每行每列台数，再扫每个服务器：所在行或列计数大于 $1$ 则计入。两次遍历，额外 $O (m + n)$ 。

我们可以统计每一行、每一列的服务器数量，然后遍历每个服务器，若当前服务器所在的行或者列的服务器数量超过 $1$ ，说明当前服务器满足条件，结果加 $1$ 。

遍历结束后，返回结果即可。

时间复杂度 $O (m \times n)$ ，空间复杂度 $O (m + n)$ 。其中 $m$ 和 $n$ 分别为矩阵的行数和列数。

func countServers(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	row, col := make([]int, m), make([]int, n)
	for i := range grid {
		for j, x := range grid[i] {
			row[i] += x
			col[j] += x
		}
	}
	for i := range grid {
		for j, x := range grid[i] {
			if x == 1 && (row[i] > 1 || col[j] > 1) {
				ans++
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1319. 连通网络的操作次数

中等1 种解法

标签：深度优先搜索、广度优先搜索、并查集、图

题目、示例与约束

用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。

示例 1：

输入：n = 4, connections = [[0,1],[0,2],[1,2]]
输出：1
解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。

示例 2：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
输出：2

示例 3：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
输出：-1
解释：线缆数量不足。

示例 4：

输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
输出：0

提示：

1 <= n <= 10^5
1 <= connections.length <= min(n*(n-1)/2, 10^5)
connections[i].length == 2
0 <= connections[i][0], connections[i][1] < n
connections[i][0] != connections[i][1]
没有重复的连接。
两台计算机不会通过多条线缆连接。

方法一：并查集 · Go 实现

思考

用已有线缆把 $n$ 台机器连成一个网络，每次操作搬动一条线。 $n$ 、 $m$ 可达 $10^{5}$ ，不宜反复建图试连。连通分量数为 $k$ 时，至少需要 $k - 1$ 条多余边才能拼成一棵生成树。

并查集扫描边：两端已在同一集合则记为冗余，否则合并并减少分量。若冗余边少于 $k - 1$ ，无法连通，返回 $- 1$ ；否则答案为 $k - 1$ 。

我们可以用并查集维护计算机之间的联通关系。遍历所有的连接，对于每个连接 $(a, b)$ ，如果 $a$ 和 $b$ 已经联通，那么这个连接是多余的，我们将多余的连接数加一；否则，我们将 $a$ 和 $b$ 连通，然后将联通分量数减一。

最后，如果联通分量数减一大于多余的连接数，说明我们无法使所有计算机联通，返回 -1；否则，返回联通分量数减一。

时间复杂度 $O (m \times \log n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 和 $m$ 分别是计算机的数量和连接的数量。

func makeConnected(n int, connections [][]int) int {
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	cnt := 0
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, e := range connections {
		pa, pb := find(e[0]), find(e[1])
		if pa == pb {
			cnt++
		} else {
			p[pa] = pb
			n--
		}
	}
	if n-1 > cnt {
		return -1
	}
	return n - 1
}

力扣原题 · Doocs 题解来源

1361. 验证二叉树

中等2 种解法

标签：树、深度优先搜索、广度优先搜索、并查集、图、二叉树

题目、示例与约束

二叉树上有 n 个节点，按从 0 到 n - 1 编号，其中节点 i 的两个子节点分别是 leftChild[i] 和 rightChild[i]。

只有所有节点能够形成且只形成一颗有效的二叉树时，返回 true；否则返回 false。

如果节点 i 没有左子节点，那么 leftChild[i] 就等于 -1。右子节点也符合该规则。

注意：节点没有值，本问题中仅仅使用节点编号。

示例 1：

输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
输出：true

示例 2：

输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
输出：false

示例 3：

输入：n = 2, leftChild = [1,0], rightChild = [-1,-1]
输出：false

提示：

n == leftChild.length == rightChild.length
1 <= n <= 10⁴
-1 <= leftChild[i], rightChild[i] <= n - 1

方法一：并查集 · Go 实现

思考

左右孩子数组描述 $n$ 个节点，判断是否恰为一棵二叉树。非法情形是多父、成环或不止一个连通块。并查集在连边时检测：孩子已有父、或两端已连通（成环）则失败；成功则合并并减少分量。最后分量必须为 $1$ 。

我们可以遍历每个节点 $i$ 以及对应的左右孩子 $l$ , $r$ ，用 $v i s$ 数组记录节点是否有父节点：

若孩子节点已存在父节点，说明有多个父亲，不满足条件，直接返回 false。
若孩子节点与父节点已经处于同一个连通分量，说明会形成环，不满足条件，直接返回 false。
否则，进行合并，并且将 $v i s$ 数组对应位置置为 true，同时将连通分量个数减去 $1$ 。

遍历结束，判断并查集中连通分量个数是否为 $1$ ，若是返回 true，否则返回 false。

时间复杂度 $O (n \times α (n))$ ，空间复杂度 $O (n)$ 。其中 $n$ 为节点个数，而 $α (n)$ 为阿克曼函数的反函数，即反阿克曼函数，其值小于 $5$ 。

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	vis := make([]bool, n)
	for i, a := range leftChild {
		for _, j := range []int{a, rightChild[i]} {
			if j != -1 {
				if vis[j] || find(i) == find(j) {
					return false
				}
				p[find(i)] = find(j)
				vis[j] = true
				n--
			}
		}
	}
	return n == 1
}

方法二：入度统计 + BFS · Go 实现

思考

并查集要维护父标记与分量。改为先数入度：没有入度 $0$ 则无根；有则从该根 BFS，遇已访问孩子说明多父或环，最后访问数须等于 $n$ 。无需并查数组。

我们可以先统计每个节点的入度，即有多少个父节点指向它。若不存在入度为 $0$ 的节点，说明图中存在环，直接返回 false；否则，该节点即为根节点。

接下来，从根节点出发进行广度优先搜索。遍历过程中，若某个子节点已被访问过，说明该节点有多个父节点或图中存在环，直接返回 false。

遍历结束后，判断访问过的节点数是否等于 $n$ ，若是则说明所有节点构成且仅构成一棵有效的二叉树，返回 true，否则返回 false。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为节点个数。

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
	indeg := make([]int, n)

	for _, c := range leftChild {
		if c != -1 {
			indeg[c]++
		}
	}
	for _, c := range rightChild {
		if c != -1 {
			indeg[c]++
		}
	}

	root := -1
	for i, x := range indeg {
		if x == 0 {
			root = i
			break
		}
	}
	if root == -1 {
		return false
	}

	q := []int{root}
	vis := map[int]bool{root: true}

	for len(q) > 0 {
		i := q[0]
		q = q[1:]

		j := leftChild[i]
		if j != -1 {
			if vis[j] {
				return false
			}
			vis[j] = true
			q = append(q, j)
		}

		j = rightChild[i]
		if j != -1 {
			if vis[j] {
				return false
			}
			vis[j] = true
			q = append(q, j)
		}
	}

	return len(vis) == n
}

力扣原题 · Doocs 题解来源

1391. 检查网格中是否存在有效路径

中等1 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵

题目、示例与约束

给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：

1 表示连接左单元格和右单元格的街道。
2 表示连接上单元格和下单元格的街道。
3 表示连接左单元格和下单元格的街道。
4 表示连接右单元格和下单元格的街道。
5 表示连接左单元格和上单元格的街道。
6 表示连接右单元格和上单元格的街道。

你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。

注意：你不能变更街道。

如果网格中存在有效的路径，则返回 true，否则返回 false 。

示例 1：

输入：grid = [[2,4,3],[6,5,2]]
输出：true
解释：如图所示，你可以从 (0, 0) 开始，访问网格中的所有单元格并到达 (m - 1, n - 1) 。

示例 2：

输入：grid = [[1,2,1],[1,2,1]]
输出：false
解释：如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你只会停在 (0, 0) 处。

示例 3：

输入：grid = [[1,1,2]]
输出：false
解释：你会停在 (0, 1)，而且无法到达 (0, 2) 。

示例 4：

输入：grid = [[1,1,1,1,1,1,3]]
输出：true

示例 5：

输入：grid = [[2],[2],[2],[2],[2],[2],[6]]
输出：true

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6

方法一 · Go 实现

思考

六种街道只连通指定的一对方向，问左上能否走到右下。把格子看成节点，仅当两侧街道的开口互相衔接才连边。并查集按街道类型把合法邻居合并，最后判断起点与终点是否同一分量。

func hasValidPath(grid [][]int) bool {
	m, n := len(grid), len(grid[0])
	p := make([]int, m*n)
	for i := range p {
		p[i] = i
	}
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	left := func(i, j int) {
		if j > 0 && (grid[i][j-1] == 1 || grid[i][j-1] == 4 || grid[i][j-1] == 6) {
			p[find(i*n+j)] = find(i*n + j - 1)
		}
	}
	right := func(i, j int) {
		if j < n-1 && (grid[i][j+1] == 1 || grid[i][j+1] == 3 || grid[i][j+1] == 5) {
			p[find(i*n+j)] = find(i*n + j + 1)
		}
	}
	up := func(i, j int) {
		if i > 0 && (grid[i-1][j] == 2 || grid[i-1][j] == 3 || grid[i-1][j] == 4) {
			p[find(i*n+j)] = find((i-1)*n + j)
		}
	}
	down := func(i, j int) {
		if i < m-1 && (grid[i+1][j] == 2 || grid[i+1][j] == 5 || grid[i+1][j] == 6) {
			p[find(i*n+j)] = find((i+1)*n + j)
		}
	}
	for i, row := range grid {
		for j, e := range row {
			if e == 1 {
				left(i, j)
				right(i, j)
			} else if e == 2 {
				up(i, j)
				down(i, j)
			} else if e == 3 {
				left(i, j)
				down(i, j)
			} else if e == 4 {
				right(i, j)
				down(i, j)
			} else if e == 5 {
				left(i, j)
				up(i, j)
			} else {
				right(i, j)
				up(i, j)
			}
		}
	}
	return find(0) == find(m*n-1)
}

力扣原题 · Doocs 题解来源

1489. 找到最小生成树里的关键边和伪关键边

困难1 种解法

标签：并查集、图、Kruskal 算法、最小生成树、Prim 算法、排序、强连通分量、Boruvka 算法

题目、示例与约束

给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [from_i, to_i, weight_i] 表示在 from_i 和 to_i 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权值和最小。

请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。

请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。

示例 1：

输入：n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
输出：[[0,1],[2,3,4,5]]
解释：上图描述了给定图。
下图是所有的最小生成树。

注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出的第一个列表。
边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。

示例 2 ：

输入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
输出：[[],[0,1,2,3]]
解释：可以观察到 4 条边都有相同的权值，任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。

提示：

2 <= n <= 100
1 <= edges.length <= min(200, n * (n - 1) / 2)
edges[i].length == 3
0 <= from_i < to_i < n
1 <= weight_i <= 1000
所有 (from_i, to_i) 数对都是互不相同的。

方法一：Kruskal 算法 · Go 实现

思考

$n \leq 100$ 、边至多 $200$ ，可多次求 MST。先 Kruskal 得到最小生成树权值 $v$ 。

一条边是关键边，当且仅当删去后无法连通或权值大于 $v$ ；否则若强制加入后仍能得到权值 $v$ ，则为伪关键边。对每条边各做一次带删除与带强制加入的 Kruskal。

先利用 Kruskal 算法，得出最小生成树的权值 v。然后依次枚举每条边，按上面的方法，判断是否是关键边；如果不是关键边，再判断是否是伪关键边。

type unionFind struct {
	p []int
	n int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	return &unionFind{p, n}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	if uf.find(a) == uf.find(b) {
		return false
	}
	uf.p[uf.find(a)] = uf.find(b)
	uf.n--
	return true
}

func findCriticalAndPseudoCriticalEdges(n int, edges [][]int) [][]int {
	for i := range edges {
		edges[i] = append(edges[i], i)
	}
	sort.Slice(edges, func(i, j int) bool {
		return edges[i][2] < edges[j][2]
	})
	v := 0
	uf := newUnionFind(n)
	for _, e := range edges {
		f, t, w := e[0], e[1], e[2]
		if uf.union(f, t) {
			v += w
		}
	}
	ans := make([][]int, 2)
	for _, e := range edges {
		f, t, w, i := e[0], e[1], e[2], e[3]
		uf = newUnionFind(n)
		k := 0
		for _, ne := range edges {
			x, y, z, j := ne[0], ne[1], ne[2], ne[3]
			if j != i && uf.union(x, y) {
				k += z
			}
		}
		if uf.n > 1 || (uf.n == 1 && k > v) {
			ans[0] = append(ans[0], i)
			continue
		}
		uf = newUnionFind(n)
		uf.union(f, t)
		k = w
		for _, ne := range edges {
			x, y, z, j := ne[0], ne[1], ne[2], ne[3]
			if j != i && uf.union(x, y) {
				k += z
			}
		}
		if k == v {
			ans[1] = append(ans[1], i)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1559. 二维网格图中探测环

中等2 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵

题目、示例与约束

给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。

一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。

同时，你也不能回到上一次移动时所在的格子。比方说，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。

如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。

示例 1：

输入：grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
输出：true
解释：如下图所示，有 2 个用不同颜色标出来的环：

示例 2：

输入：grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
输出：true
解释：如下图所示，只有高亮所示的一个合法环：

示例 3：

输入：grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
输出：false

提示：

m == grid.length
n == grid[i].length
1 <= m <= 500
1 <= n <= 500
grid 只包含小写英文字母。

方法一：BFS · Go 实现

思考

判断网格中是否存在长度至少为 $4$ 、字符相同的环。 $m, n$ 不大，一次图搜索即可，但必须排除立刻走回父格造成的假环。

对每个未访问格做广度优先：只走向同字符邻居，并记下父坐标。若邻居已被访问且不是父格，则找到环。同一连通块只搜一次。

我们可以遍历二维网格中的每一个格子，对于每一个格子，如果格子 $g r i d [i] [j]$ 未被访问过，我们就从该格子开始进行广度优先搜索，搜索过程中，我们需要记录每一个格子的父节点，以及上一个格子的坐标，如果下一个格子的值与当前格子的值相同，且不是上一个格子，并且已经被访问过，那么就说明存在环，返回 $true$ 。遍历完所有格子后，如果没有找到环，返回 $false$ 。

时间复杂度 $O (m \times n)$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别是二维网格的行数和列数。

func containsCycle(grid [][]byte) bool {
	m, n := len(grid), len(grid[0])
	vis := make([][]bool, m)
	for i := range vis {
		vis[i] = make([]bool, n)
	}
	dirs := []int{-1, 0, 1, 0, -1}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if !vis[i][j] {
				q := [][]int{{i, j, -1, -1}}
				vis[i][j] = true

				for len(q) > 0 {
					p := q[0]
					q = q[1:]
					x, y, px, py := p[0], p[1], p[2], p[3]

					for k := 0; k < 4; k++ {
						nx, ny := x+dirs[k], y+dirs[k+1]
						if nx >= 0 && nx < m && ny >= 0 && ny < n {
							if grid[nx][ny] != grid[x][y] || (nx == px && ny == py) {
								continue
							}
							if vis[nx][ny] {
								return true
							}
							q = append(q, []int{nx, ny, x, y})
							vis[nx][ny] = true
						}
					}
				}
			}
		}
	}
	return false
}

方法二：DFS · Go 实现

思考

广度优先需要显式队列，深度优先用递归栈表达同一父指针判定，代码更短。访问标记与「非父且已访问则为环」的规则不变，只是遍历次序不同。

我们可以遍历二维网格中的每一个格子，对于每一个格子，如果格子 $g r i d [i] [j]$ 未被访问过，我们就从该格子开始进行深度优先搜索，搜索过程中，我们需要记录每一个格子的父节点，以及上一个格子的坐标，如果下一个格子的值与当前格子的值相同，且不是上一个格子，并且已经被访问过，那么就说明存在环，返回 $true$ 。遍历完所有格子后，如果没有找到环，返回 $false$ 。

时间复杂度 $O (m \times n)$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别是二维网格的行数和列数。

func containsCycle(grid [][]byte) bool {
	m, n := len(grid), len(grid[0])
	vis := make([][]bool, m)
	for i := range vis {
		vis[i] = make([]bool, n)
	}
	dirs := []int{-1, 0, 1, 0, -1}
	var dfs func(x, y, px, py int) bool
	dfs = func(x, y, px, py int) bool {
		vis[x][y] = true
		for k := 0; k < 4; k++ {
			nx, ny := x+dirs[k], y+dirs[k+1]
			if nx >= 0 && nx < m && ny >= 0 && ny < n {
				if grid[nx][ny] != grid[x][y] || (nx == px && ny == py) {
					continue
				}
				if vis[nx][ny] || dfs(nx, ny, x, y) {
					return true
				}
			}
		}
		return false
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if !vis[i][j] && dfs(i, j, -1, -1) {
				return true
			}
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

1569. 将子数组重新排序得到同一个二叉搜索树的方案数

困难1 种解法

标签：树、并查集、二叉搜索树、记忆化、数组、数学、分治、动态规划、二叉树、组合数学、费马小定理

题目、示例与约束

给你一个数组 nums 表示 1 到 n 的一个排列。我们按照元素在 nums 中的顺序依次插入一个初始为空的二叉搜索树（BST）。请你统计将 nums 重新排序后，统计满足如下条件的方案数：重排后得到的二叉搜索树与 nums 原本数字顺序得到的二叉搜索树相同。

比方说，给你 nums = [2,1,3]，我们得到一棵 2 为根，1 为左孩子，3 为右孩子的树。数组 [2,3,1] 也能得到相同的 BST，但 [3,2,1] 会得到一棵不同的 BST 。

请你返回重排 nums 后，与原数组 nums 得到相同二叉搜索树的方案数。

由于答案可能会很大，请将结果对 10⁹ + 7 取余数。

示例 1：

输入：nums = [2,1,3]
输出：1
解释：我们将 nums 重排， [2,3,1] 能得到相同的 BST 。没有其他得到相同 BST 的方案了。

示例 2：

输入：nums = [3,4,5,1,2]
输出：5
解释：下面 5 个数组会得到相同的 BST：
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]

示例 3：

输入：nums = [1,2,3]
输出：0
解释：没有别的排列顺序能得到相同的 BST 。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= nums.length
nums 中所有数 互不相同 。

方法一：组合计数 + 递归 · Go 实现

思考

统计能建出与 $n u m s$ 相同 BST 的重排个数（不含原序列本身）。 $n \leq 1000$ ，枚举排列不可行。BST 的根必须是序列首位，左右子树元素集合由大小关系唯一确定，内部次序可递归计数。

左右子树的相对顺序可任意交错，方案数为 $C_{m + n}^{m}$ 乘上两侧各自的方案数。预处理组合数后递归求解，最后减一去掉原序列。

我们设计一个函数 $d f s (n u m s)$ ，它的功能是计算以 $n u m s$ 为节点构成的二叉搜索树的方案数。那么答案就是 $d f s (n u m s) - 1$ ，因为 $d f s (n u m s)$ 计算的是以 $n u m s$ 为节点构成的二叉搜索树的方案数，而题目要求的是重排后与原数组 $n u m s$ 得到相同二叉搜索树的方案数，因此答案需要减去一。

接下来，我们来看一下 $d f s (n u m s)$ 的计算方法。

对于一个数组 $n u m s$ ，它的第一个元素是根节点，那么它的左子树的元素都小于它，右子树的元素都大于它。因此，我们可以将数组分为三部分，第一部分是根节点，第二部分是左子树的元素，记为 $l e f t$ ，第三部分是右子树的元素，记为 $r i g h t$ 。那么，左子树的元素个数为 $m$ ，右子树的元素个数为 $n$ ，那么 $l e f t$ 和 $r i g h t$ 的方案数分别为 $d f s (l e f t)$ 和 $d f s (r i g h t)$ 。我们可以在数组 $n u m s$ 的 $m + n$ 个位置中选择 $m$ 个位置放置左子树的元素，剩下的 $n$ 个位置放置右子树的元素，这样就能保证重排后与原数组 $n u m s$ 得到相同二叉搜索树。因此， $d f s (n u m s)$ 的计算方法为：

d f s (n u m s) = C_{m + n}^{m} \times d f s (l e f t) \times d f s (r i g h t)

其中 $C_{m + n}^{m}$ 表示从 $m + n$ 个位置中选择 $m$ 个位置的方案数，我们可以通过预处理得到。

注意答案的取模运算，因为 $d f s (n u m s)$ 的值可能会很大，所以我们需要在计算过程中对每一步的结果取模，最后再对整个结果取模。

时间复杂度 $O (n^{2})$ ，空间复杂度 $O (n^{2})$ 。其中 $n$ 是数组 $n u m s$ 的长度。

func numOfWays(nums []int) int {
	n := len(nums)
	const mod = 1e9 + 7
	c := make([][]int, n)
	for i := range c {
		c[i] = make([]int, n)
	}
	c[0][0] = 1
	for i := 1; i < n; i++ {
		c[i][0] = 1
		for j := 1; j <= i; j++ {
			c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod
		}
	}
	var dfs func(nums []int) int
	dfs = func(nums []int) int {
		if len(nums) < 2 {
			return 1
		}
		var left, right []int
		for _, x := range nums[1:] {
			if x < nums[0] {
				left = append(left, x)
			} else {
				right = append(right, x)
			}
		}
		m, n := len(left), len(right)
		a, b := dfs(left), dfs(right)
		return c[m+n][m] * a % mod * b % mod
	}
	return (dfs(nums) - 1 + mod) % mod
}

力扣原题 · Doocs 题解来源

1579. 保证图可完全遍历

困难1 种解法

标签：并查集、图

题目、示例与约束

Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3 种类型的边：

类型 1：只能由 Alice 遍历。
类型 2：只能由 Bob 遍历。
类型 3：Alice 和 Bob 都可以遍历。

给你一个数组 edges ，其中 edges[i] = [type_i, u_i, v_i] 表示节点 u_i 和 v_i 之间存在类型为 type_i 的双向边。请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。

返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。

示例 1：

输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
输出：2
解释：如果删除 [1,1,2] 和 [1,1,3] 这两条边，Alice 和 Bob 仍然可以完全遍历这个图。再删除任何其他的边都无法保证图可以完全遍历。所以可以删除的最大边数是 2 。

示例 2：

输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
输出：0
解释：注意，删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。

示例 3：

输入：n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
输出：-1
解释：在当前图中，Alice 无法从其他节点到达节点 4 。类似地，Bob 也不能达到节点 1 。因此，图无法完全遍历。

提示：

1 <= n <= 10^5
1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)
edges[i].length == 3
1 <= edges[i][0] <= 3
1 <= edges[i][1] < edges[i][2] <= n
所有元组 (type_i, u_i, v_i) 互不相同

方法一：贪心 + 并查集 · Go 实现

思考

删除尽量多的边，使 Alice 与 Bob 仍都能走遍全图。 $n$ 与边数达 $10^{5}$ ，不能枚举子集。公共边两人都能用，应优先保留；独占边只在各自图上补连通。

两个并查集分别维护两人的连通性。先加类型 $3$ ：若两端已连通则这条公共边可删。再分别加类型 $1$ 、 $2$ ，同样把成环的边计入删除数。最后两人的连通块数都为 $1$ 才有解。

题目要求我们删除最多数目的边，使得 Alice 和 Bob 都可以遍历整个图。也即是说，我们需要保留尽可能少的边，并且要求这些边能够使得 Alice 和 Bob 都可以遍历整个图。

我们可以用两个并查集 $u f a$ 和 $u f b$ 分别维护 Alice 和 Bob 的遍历情况。

接下来，我们优先遍历公共边，即 $t y p e = 3$ 的边。对于每一条公共边的两个端点 $u$ 和 $v$ ，如果这两个点已经在同一个连通分量中，那么我们就可以删去这条边，因此答案加一；否则我们就将这两个点合并，即执行 $u f a . u n i o n (u, v)$ 和 $u f b . u n i o n (u, v)$ 。

然后，我们再遍历 Alice 独有的边，即 $t y p e = 1$ 的边。对于每一条 Alice 独有的边的两个端点 $u$ 和 $v$ ，如果这两个点已经在同一个连通分量中，那么我们就可以删去这条边，答案加一；否则我们就将这两个点合并，即执行 $u f a . u n i o n (u, v)$ 。同理，对于 Bob 独有的边，我们也可以执行相同的操作。

最后，如果 Alice 和 Bob 都可以遍历整个图，那么答案就是我们删除的边数；否则答案就是 $- 1$ 。

时间复杂度 $O (m \times α (n))$ ，空间复杂度 $O (n)$ 。其中 $m$ 是边数，而 $α (n)$ 是阿克曼函数的反函数。

type unionFind struct {
	p, size []int
	cnt     int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size, n}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a-1), uf.find(b-1)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	uf.cnt--
	return true
}

func maxNumEdgesToRemove(n int, edges [][]int) (ans int) {
	ufa := newUnionFind(n)
	ufb := newUnionFind(n)
	for _, e := range edges {
		t, u, v := e[0], e[1], e[2]
		if t == 3 {
			if ufa.union(u, v) {
				ufb.union(u, v)
			} else {
				ans++
			}
		}
	}
	for _, e := range edges {
		t, u, v := e[0], e[1], e[2]
		if t == 1 && !ufa.union(u, v) {
			ans++
		}
		if t == 2 && !ufb.union(u, v) {
			ans++
		}
	}
	if ufa.cnt == 1 && ufb.cnt == 1 {
		return
	}
	return -1
}

力扣原题 · Doocs 题解来源

1584. 连接所有点的最小费用

中等2 种解法

标签：并查集、图、数组、Kruskal 算法、最小生成树、Prim 算法、Boruvka 算法

题目、示例与约束

给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [x_i, y_i] 。

连接点 [x_i, y_i] 和点 [x_j, y_j] 的费用为它们之间的 曼哈顿距离 ：|x_i - x_j| + |y_i - y_j| ，其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。

示例 1：

输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
解释：

我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。

示例 2：

输入：points = [[3,12],[-2,5],[-4,1]]
输出：18

示例 3：

输入：points = [[0,0],[1,1],[1,0],[-1,1]]
输出：4

示例 4：

输入：points = [[-1000000,-1000000],[1000000,1000000]]
输出：4000000

示例 5：

输入：points = [[0,0]]
输出：0

提示：

1 <= points.length <= 1000
-10⁶ <= x_i, y_i <= 10⁶
所有点 (x_i, y_i) 两两不同。

方法一：朴素 Prim 算法 · Go 实现

思考

用曼哈顿距离连接全部点，求最小生成树。点数 $n \leq 1000$ ，完全图有 $O (n^{2})$ 条边，适合稠密图算法。

朴素 Prim：维护每个点到当前树的距离，每次选未访问的最近顶点加入，并用它更新其余点。 $n$ 轮、每轮扫 $n$ 个点，时间为 $O (n^{2})$ 。

我们定义一个数组 $d i s t$ ，其中 $d i s t [i]$ 表示点 $i$ 到当前生成树的距离，初始时 $d i s t [0] = 0$ ，其余均为 $+ \infty$ ，定义一个数组 $v i s$ ，其中 $v i s [i]$ 表示点 $i$ 是否在生成树中，初始时所有点均不在生成树中，定义一个二维数组 $g$ ，其中 $g [i] [j]$ 表示点 $i$ 到点 $j$ 的距离，那么我们的目标是将所有点都加入到生成树中，且总费用最小。

我们每次从不在生成树中的点中选取一个距离最小的点 $i$ ，将点 $i$ 加入到生成树中，并将 $i$ 到其它点的距离更新到 $d i s t$ 数组中，直到所有点都在生成树中为止。

该算法适用于稠密图，时间复杂度 $O (n^{2})$ ，空间复杂度 $O (n^{2})$ 。其中 $n$ 为点的数量。

func minCostConnectPoints(points [][]int) (ans int) {
	n := len(points)
	g := make([][]int, n)
	vis := make([]bool, n)
	dist := make([]int, n)
	for i := range g {
		g[i] = make([]int, n)
		dist[i] = 1 << 30
	}
	for i := range g {
		x1, y1 := points[i][0], points[i][1]
		for j := i + 1; j < n; j++ {
			x2, y2 := points[j][0], points[j][1]
			t := abs(x1-x2) + abs(y1-y2)
			g[i][j] = t
			g[j][i] = t
		}
	}
	dist[0] = 0
	for i := 0; i < n; i++ {
		j := -1
		for k := 0; k < n; k++ {
			if !vis[k] && (j == -1 || dist[k] < dist[j]) {
				j = k
			}
		}
		vis[j] = true
		ans += dist[j]
		for k := 0; k < n; k++ {
			if !vis[k] {
				dist[k] = min(dist[k], g[j][k])
			}
		}
	}
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

方法二：Kruskal 算法 · Go 实现

思考

Prim 始终维护切边，实现依赖邻接矩阵。Kruskal 则把全部边按权排序，用并查集按序加边，连通时即停。边数为 $O (n^{2})$ ，排序占主导，适合希望按边处理的写法。

我们先将所有边按照长度由小到大进行排序，循环遍历每条边，逐个加入到图中，当所有点达到一个连通状态时，退出循环，返回此时的总费用即可。

时间复杂度 $O (m \times \log m)$ ，空间复杂度 $O (m)$ 。其中 $m$ 为边的数量，本题中 $m = n^{2}$ 。

func minCostConnectPoints(points [][]int) int {
	n := len(points)
	var g [][]int
	for i, p := range points {
		x1, y1 := p[0], p[1]
		for j := i + 1; j < n; j++ {
			x2, y2 := points[j][0], points[j][1]
			g = append(g, []int{abs(x1-x2) + abs(y1-y2), i, j})
		}
	}
	sort.Slice(g, func(i, j int) bool {
		return g[i][0] < g[j][0]
	})
	ans := 0
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(x int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, e := range g {
		cost, i, j := e[0], e[1], e[2]
		if find(i) == find(j) {
			continue
		}
		p[find(i)] = find(j)
		ans += cost
		n--
		if n == 1 {
			return ans
		}
	}
	return 0
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

1627. 带阈值的图连通性

困难1 种解法

标签：并查集、数组、数学、数论

题目、示例与约束

有 n 座城市，编号从 1 到 n 。编号为 x 和 y 的两座城市直接连通的前提是： x 和 y 的公因数中，至少有一个 严格大于 某个阈值 threshold 。更正式地说，如果存在整数 z ，且满足以下所有条件，则编号 x 和 y 的城市之间有一条道路：

x % z == 0
y % z == 0
z > threshold

给你两个整数 n 和 threshold ，以及一个待查询数组，请你判断每个查询 queries[i] = [a_i, b_i] 指向的城市 a_i 和 b_i 是否连通（即，它们之间是否存在一条路径）。

返回数组 answer ，其中answer.length == queries.length 。如果第 i 个查询中指向的城市 a_i 和 b_i 连通，则 answer[i] 为 true ；如果不连通，则 answer[i] 为 false 。

示例 1：

输入：n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]]
输出：[false,false,true]
解释：每个数的因数如下：
1:   1
2:   1, 2
3:   1, 3
4:   1, 2, 4
5:   1, 5
6:   1, 2, 3, 6
所有大于阈值的的因数已经加粗标识，只有城市 3 和 6 共享公约数 3 ，因此结果是： 
[1,4]   1 与 4 不连通
[2,5]   2 与 5 不连通
[3,6]   3 与 6 连通，存在路径 3--6

示例 2：

输入：n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]]
输出：[true,true,true,true,true]
解释：每个数的因数与上一个例子相同。但是，由于阈值为 0 ，所有的因数都大于阈值。因为所有的数字共享公因数 1 ，所以所有的城市都互相连通。

示例 3：

输入：n = 5, threshold = 1, queries = [[4,5],[4,5],[3,2],[2,3],[3,4]]
输出：[false,false,false,false,false]
解释：只有城市 2 和 4 共享的公约数 2 严格大于阈值 1 ，所以只有这两座城市是连通的。
注意，同一对节点 [x, y] 可以有多个查询，并且查询 [x，y] 等同于查询 [y，x] 。

提示：

2 <= n <= 10⁴
0 <= threshold <= n
1 <= queries.length <= 10⁵
queries[i].length == 2
1 <= a_i, b_i <= cities
a_i != b_i

方法一：并查集 · Go 实现

思考

两城连通当存在一条公约数大于 $threshold$ 的边链。若对每对城市试 $gcd$ ，询问与 $n$ 都可达 $10^{4}$ 量级时过慢。

大于阈值的每个 $z$ 会把它的倍数全部连在一起，预先按倍数连边即可覆盖全部直接边。

并查集在 $z \in (threshold, n]$ 上把 $z, 2 z, 3 z, \dots$ 合并，每个询问判断两点是否同根。

我们可以枚举 $z$ 以及 $z$ 的倍数，用并查集将它们连通起来。这样，对于每个查询 $[a, b]$ ，我们只需要判断 $a$ 和 $b$ 是否在同一个连通块中即可。

时间复杂度 $O (n \times \log n \time (α (n) + q))$ ，空间复杂度 $O (n)$ 。其中 $n$ 和 $q$ 分别是节点数和查询数，而 $α$ 是阿克曼函数的反函数。

type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func areConnected(n int, threshold int, queries [][]int) []bool {
	uf := newUnionFind(n + 1)
	for a := threshold + 1; a <= n; a++ {
		for b := a + a; b <= n; b += a {
			uf.union(a, b)
		}
	}
	ans := make([]bool, len(queries))
	for i, q := range queries {
		ans[i] = uf.find(q[0]) == uf.find(q[1])
	}
	return ans
}

力扣原题 · Doocs 题解来源

1631. 最小体力消耗路径

中等3 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、二分查找、矩阵、Dijkstra 算法、堆（优先队列）

题目、示例与约束

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往上，下，左，右四个方向之一移动，你想要找到耗费体力最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值 。

示例 1：

输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。

示例 2：

输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
输出：1
解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。

示例 3：

输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
输出：0
解释：上图所示路径不需要消耗任何体力。

提示：

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10⁶

方法一：并查集 · Go 实现

思考

路径代价是相邻高度差的最大值，求左上到右下的最小可能代价。若二分答案，每次还要搜连通性；也可以把格子当点、高度差当边权，按权从小到大连边。

并查集按边权升序合并，一旦起点与终点连通，当前边权即为最小瓶颈。

先收集四连通边并排序，再依次 $union$ ，用 $connected (0, m n - 1)$ 作为停止条件。

对于本题，我们可以把每个格子当做图的一个节点，把相邻两个格子的高度差绝对值当做边的权重，因此本题是求解从最左上角的节点到最右下角的节点的连通性问题。

我们先构建一个边集，然后按照边的权重从小到大进行排序，逐个添加边，直到最左上角的节点和最右下角的节点连通为止，此时的边的权重就是题目的最小体力消耗值。

时间复杂度 $O (m \times n \times \log (m \times n))$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别是二维数组的行数和列数。

type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func (uf *unionFind) connected(a, b int) bool {
	return uf.find(a) == uf.find(b)
}

func minimumEffortPath(heights [][]int) int {
	m, n := len(heights), len(heights[0])
	edges := make([][3]int, 0, m*n*2)
	dirs := [3]int{0, 1, 0}
	for i, row := range heights {
		for j, h := range row {
			for k := 0; k < 2; k++ {
				x, y := i+dirs[k], j+dirs[k+1]
				if x >= 0 && x < m && y >= 0 && y < n {
					edges = append(edges, [3]int{abs(h - heights[x][y]), i*n + j, x*n + y})
				}
			}
		}
	}
	sort.Slice(edges, func(i, j int) bool { return edges[i][0] < edges[j][0] })
	uf := newUnionFind(m * n)
	for _, e := range edges {
		uf.union(e[1], e[2])
		if uf.connected(0, m*n-1) {
			return e[0]
		}
	}
	return 0
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

方法二：二分查找 + BFS · Go 实现

思考

方法一需要排序全部边。代价 $h$ 可行当且仅当只走差值 $\leq h$ 的边能从起点到达终点，该判定关于 $h$ 单调。

在 $[0, 10^{6}]$ 上二分 $h$ ，每次 BFS 检验，从而不必维护并查集。

我们注意到，如果一个路径的最大体力消耗值为 $x$ ，那么对于任意 $y > x$ ，该路径也是满足条件的，这存在着单调性，因此我们可以使用二分查找的方法，找到最小的满足条件的体力消耗值。

我们定义二分查找的左边界 $l = 0$ ，右边界 $r = 10^{6}$ ，每次取 $m i d = (l + r) / 2$ ，然后使用 BFS 判断是否存在一条从左上角到右下角的路径，使得路径上相邻节点的高度差绝对值都不大于 $m i d$ ，如果存在，那么说明 $m i d$ 还有可能是最小的满足条件的体力消耗值，因此令 $r = m i d$ ，否则令 $l = m i d + 1$ 。

时间复杂度 $O (m \times n \times \log M)$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别是二维数组的行数和列数，而 $M$ 是二维数组中的最大值，本题中 $M = 10^{6}$ 。

func minimumEffortPath(heights [][]int) int {
	return sort.Search(1e6, func(h int) bool {
		m, n := len(heights), len(heights[0])
		vis := make([][]bool, m)
		for i := range vis {
			vis[i] = make([]bool, n)
		}
		vis[0][0] = true
		q := [][2]int{}
		q = append(q, [2]int{0, 0})
		dirs := [5]int{-1, 0, 1, 0, -1}
		for len(q) > 0 {
			p := q[0]
			q = q[1:]
			i, j := p[0], p[1]
			if i == m-1 && j == n-1 {
				return true
			}
			for k := 0; k < 4; k++ {
				x, y := i+dirs[k], j+dirs[k+1]
				if x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && abs(heights[x][y]-heights[i][j]) <= h {
					vis[x][y] = true
					q = append(q, [2]int{x, y})
				}
			}
		}
		return false
	})
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

方法三：堆优化的 Dijkstra 算法 · Go 实现

思考

前两法分别依赖全局排序或反复搜图。把边权看成「走到邻格后的新瓶颈」，则是最短路，只是松弛用 $max$ 而非加法。

堆优化 Dijkstra 维护到各格的最小瓶颈 $d i s t$ ，弹出时向四邻松弛 $max (t, | h_{i} - h_{j} |)$ ，终点即为答案。

我们可以把每个格子当做图的一个节点，把相邻两个格子的高度差绝对值当做边的权重，因此本题是求解从最左上角的节点到最右下角的节点的最短路径问题。

我们可以使用 Dijkstra 算法求解最短路径，使用优先队列（堆）来优化时间复杂度。具体地，我们维护一个大小为 $m \times n$ 的二维数组 $d i s t$ ，其中 $d i s t [i] [j]$ 表示从左上角到节点 $(i, j)$ 的最短路径的最大权重，初始时 $d i s t [0] [0] = 0$ ，其余元素均为正无穷大。

我们用优先队列（堆）来存储节点，每次从优先队列（堆）中取出权重最小的节点，然后更新其相邻节点的权重，如果相邻节点的权重发生了改变，那么就把该节点加入优先队列（堆）中。当优先队列（堆）为空时，说明我们已经找到了最短路径。

时间复杂度 $O (m \times n \times \log (m \times n))$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别是二维数组的行数和列数。

func minimumEffortPath(heights [][]int) int {
	m, n := len(heights), len(heights[0])
	dist := make([][]int, m)
	for i := range dist {
		dist[i] = make([]int, n)
		for j := range dist[i] {
			dist[i][j] = 1 << 30
		}
	}
	dirs := [5]int{-1, 0, 1, 0, -1}
	dist[0][0] = 0
	pq := hp{}
	heap.Push(&pq, tuple{0, 0, 0})
	for pq.Len() > 0 {
		p := heap.Pop(&pq).(tuple)
		t, i, j := p.t, p.i, p.j
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < m && y >= 0 && y < n {
				if d := max(t, abs(heights[x][y]-heights[i][j])); d < dist[x][y] {
					dist[x][y] = d
					heap.Push(&pq, tuple{d, x, y})
				}
			}
		}
	}
	return dist[m-1][n-1]
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

type tuple struct{ t, i, j int }
type hp []tuple

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].t < h[j].t }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

力扣原题 · Doocs 题解来源

1632. 矩阵转换后的排名

困难1 种解法

标签：并查集、图、拓扑排序、数组、矩阵、排序

题目、示例与约束

给你一个 m x n 的矩阵 matrix ，请你返回一个新的矩阵 answer ，其中 answer[row][col] 是 matrix[row][col] 的排名。

每个元素的排名是一个整数，表示这个元素相对于其他元素的大小关系，它按照如下规则计算：

排名是从 1 开始的一个整数。
如果两个元素 p 和 q 在 同一行 或者 同一列 ，那么：
- 如果 p < q ，那么 rank(p) < rank(q)
- 如果 p == q ，那么 rank(p) == rank(q)
- 如果 p > q ，那么 rank(p) > rank(q)
排名需要越小越好。

题目保证按照上面规则 answer 数组是唯一的。

示例 1：

输入：matrix = [[1,2],[3,4]]
输出：[[1,2],[2,3]]
解释：
matrix[0][0] 的排名为 1 ，因为它是所在行和列的最小整数。
matrix[0][1] 的排名为 2 ，因为 matrix[0][1] > matrix[0][0] 且 matrix[0][0] 的排名为 1 。
matrix[1][0] 的排名为 2 ，因为 matrix[1][0] > matrix[0][0] 且 matrix[0][0] 的排名为 1 。
matrix[1][1] 的排名为 3 ，因为 matrix[1][1] > matrix[0][1]， matrix[1][1] > matrix[1][0] 且 matrix[0][1] 和 matrix[1][0] 的排名都为 2 。

示例 2：

输入：matrix = [[7,7],[7,7]]
输出：[[1,1],[1,1]]

示例 3：

输入：matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
输出：[[4,2,3],[1,3,4],[5,1,6],[1,3,4]]

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 500
-10⁹ <= matrix[row][col] <= 10⁹

方法一：排序 + 并查集 · Go 实现

思考

秩由同行同列中更小的值决定，相同值还必须同秩。若无重复，按值从小到大扫描、取所在行与列已有最大秩加一即可； $m, n \leq 500$ 且存在重复时，同值可能通过「同行/同列」连锁。

把同一数值的格子按行、列并查（列编号平移 $m$ ），每个连通块共享「块内行、列最大秩加一」。

按值排序处理，用行、列最大秩数组更新答案后重置并查集，以免不同数值互相粘连。

我们先考虑简化情形：没有相同的元素。那么显然最小的元素的秩为 $1$ ，第二小的元素则要考虑是否和最小元素同行或同列。于是得到贪心解法：从小到大遍历元素，并维护每行、每列的最大秩，该元素的秩即为同行、同列的最大秩加 $1$ 。见题目：2371. 最小化网格中的最大值。

存在相同元素时则较为复杂，假设两个相同元素同行（或同列），那么就要考虑到两个元素分别对应的行（或列）的最大秩。同时还可能出现联动，比如元素 a 和 b 同行，b 和 c 同列，那么要同时考虑这三个元素。

这种联动容易想到并查集，于是我们用并查集将元素分为几个连通块，对于每个连通块，里面所有元素对应的行或列的最大秩加 $1$ ，即为该连通块内所有元素的秩。

时间复杂度 $O (m \times n \times \log (m \times n))$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别为矩阵的行数和列数。

type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) {
	pa, pb := uf.find(a), uf.find(b)
	if pa != pb {
		if uf.size[pa] > uf.size[pb] {
			uf.p[pb] = pa
			uf.size[pa] += uf.size[pb]
		} else {
			uf.p[pa] = pb
			uf.size[pb] += uf.size[pa]
		}
	}
}

func (uf *unionFind) reset(x int) {
	uf.p[x] = x
	uf.size[x] = 1
}

func matrixRankTransform(matrix [][]int) [][]int {
	m, n := len(matrix), len(matrix[0])
	type pair struct{ i, j int }
	d := map[int][]pair{}
	for i, row := range matrix {
		for j, v := range row {
			d[v] = append(d[v], pair{i, j})
		}
	}
	rowMax := make([]int, m)
	colMax := make([]int, n)
	ans := make([][]int, m)
	for i := range ans {
		ans[i] = make([]int, n)
	}
	vs := []int{}
	for v := range d {
		vs = append(vs, v)
	}
	sort.Ints(vs)
	uf := newUnionFind(m + n)
	rank := make([]int, m+n)
	for _, v := range vs {
		ps := d[v]
		for _, p := range ps {
			uf.union(p.i, p.j+m)
		}
		for _, p := range ps {
			i, j := p.i, p.j
			rank[uf.find(i)] = max(rank[uf.find(i)], max(rowMax[i], colMax[j]))
		}
		for _, p := range ps {
			i, j := p.i, p.j
			ans[i][j] = 1 + rank[uf.find(i)]
			rowMax[i], colMax[j] = ans[i][j], ans[i][j]
		}
		for _, p := range ps {
			uf.reset(p.i)
			uf.reset(p.j + m)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1697. 检查边长度限制的路径是否存在

困难1 种解法

标签：并查集、图、数组、双指针、排序

题目、示例与约束

给你一个 n 个点组成的无向图边集 edgeList ，其中 edgeList[i] = [u_i, v_i, dis_i] 表示点 u_i 和点 v_i 之间有一条长度为 dis_i 的边。请注意，两个点之间可能有 超过一条边 。

给你一个查询数组queries ，其中 queries[j] = [p_j, q_j, limit_j] ，你的任务是对于每个查询 queries[j] ，判断是否存在从 p_j 到 q_j的路径，且这条路径上的每一条边都 严格小于 limit_j 。

请你返回一个 布尔数组 answer ，其中 answer.length == queries.length ，当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false 。

示例 1：

输入：n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
输出：[false,true]
解释：上图为给定的输入数据。注意到 0 和 1 之间有两条重边，分别为 2 和 16 。
对于第一个查询，0 和 1 之间没有小于 2 的边，所以我们返回 false 。
对于第二个查询，有一条路径（0 -> 1 -> 2）两条边都小于 5 ，所以这个查询我们返回 true 。

示例 2：

输入：n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
输出：[true,false]
解释：上图为给定数据。

提示：

2 <= n <= 10⁵
1 <= edgeList.length, queries.length <= 10⁵
edgeList[i].length == 3
queries[j].length == 3
0 <= u_i, v_i, p_j, q_j <= n - 1
u_i != v_i
p_j != q_j
1 <= dis_i, limit_j <= 10⁹
两个点之间可能有多条边。

方法一：离线查询 + 并查集 · Go 实现

思考

多次询问两点之间是否存在所有边权都严格小于 $limit$ 的路径。在线对每问重建图过慢，询问之间互相独立，可离线。

边与询问都按权/限制升序，双指针把权小于当前 $limit$ 的边加入并查集，再查询两点是否同根。

用下标记下原询问顺序，填回答案数组。

根据题目要求，我们需要对每个查询 $q u e r i e s [i]$ 进行判断，即判断当前查询的两个点 $a$ 和 $b$ 之间是否存在一条边权小于等于 $l i m i t$ 的路径。

判断两点是否连通可以通过并查集来实现。另外，由于查询的顺序对结果没有影响，因此我们可以先将所有查询按照 $l i m i t$ 从小到大排序，所有边也按照边权从小到大排序。

然后对于每个查询，我们从边权最小的边开始，将边权严格小于 $l i m i t$ 的所有边加入并查集，接着利用并查集的查询操作判断两点是否连通即可。

时间复杂度 $O (m \times \log m + q \times \log q)$ ，其中 $m$ 和 $q$ 分别为边数和查询数。

func distanceLimitedPathsExist(n int, edgeList [][]int, queries [][]int) []bool {
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	sort.Slice(edgeList, func(i, j int) bool { return edgeList[i][2] < edgeList[j][2] })
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	m := len(queries)
	qid := make([]int, m)
	ans := make([]bool, m)
	for i := range qid {
		qid[i] = i
	}
	sort.Slice(qid, func(i, j int) bool { return queries[qid[i]][2] < queries[qid[j]][2] })
	j := 0
	for _, i := range qid {
		a, b, limit := queries[i][0], queries[i][1], queries[i][2]
		for j < len(edgeList) && edgeList[j][2] < limit {
			u, v := edgeList[j][0], edgeList[j][1]
			p[find(u)] = find(v)
			j++
		}
		ans[i] = find(a) == find(b)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1722. 执行交换操作后的最小汉明距离

中等1 种解法

标签：深度优先搜索、并查集、数组

题目、示例与约束

给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [a_i, b_i] 表示你可以交换数组 source 中下标为 a_i 和 b_i（下标从 0 开始）的两个元素。注意，你可以按任意顺序多次交换一对特定下标指向的元素。

相同长度的两个数组 source 和 target 间的 汉明距离 是元素不同的下标数量。形式上，其值等于满足 source[i] != target[i] （下标从 0 开始）的下标 i（0 <= i <= n-1）的数量。

在对数组 source 执行任意数量的交换操作后，返回 source 和 target 间的 最小汉明距离 。

示例 1：

输入：source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
输出：1
解释：source 可以按下述方式转换：
- 交换下标 0 和 1 指向的元素：source = [2,1,3,4]
- 交换下标 2 和 3 指向的元素：source = [2,1,4,3]
source 和 target 间的汉明距离是 1 ，二者有 1 处元素不同，在下标 3 。

示例 2：

输入：source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
输出：2
解释：不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。

示例 3：

输入：source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
输出：0

提示：

n == source.length == target.length
1 <= n <= 10⁵
1 <= source[i], target[i] <= 10⁵
0 <= allowedSwaps.length <= 10⁵
allowedSwaps[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i

方法一：并查集 + 哈希表 · Go 实现

思考

允许交换的下标对可以复合，同一连通分量内的值任意重排。 $n \leq 10^{5}$ ，需按分量处理而不能枚举排列。

并查集把可交换下标连成分量。每个分量内， $source$ 的多重集应尽量覆盖 $target$ 对应位置。

用分量哈希表统计源值频次；扫 $target$ 时若分量中该值已用尽则汉明距离加一。

我们可以将每个下标看作一个节点，每个下标对应的元素看作节点的值，那么给定的 allowedSwaps 中的每个元素 [a_i, b_i] 就表示下标 a_i 和 b_i 之间存在一条边。因此，我们可以使用并查集来维护这些连通分量。

在得到每个连通分量之后，我们再用二维哈希表 $c n t$ 分别统计每个连通分量中每个元素出现的次数，最后对于数组 target 中的每个元素，如果其在对应的连通分量中出现的次数大于 0，则将其出现次数减 1，否则将答案加 1。

时间复杂度 $O (n \times \log n)$ 或 $O (n \times α (n))$ ，空间复杂度 $O (n)$ 。其中 $n$ 是数组的长度，而 $α$ 是阿克曼函数的反函数。

func minimumHammingDistance(source []int, target []int, allowedSwaps [][]int) (ans int) {
	n := len(source)
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, a := range allowedSwaps {
		p[find(a[0])] = find(a[1])
	}
	cnt := map[int]map[int]int{}
	for i, x := range source {
		j := find(i)
		if cnt[j] == nil {
			cnt[j] = map[int]int{}
		}
		cnt[j][x]++
	}
	for i, x := range target {
		j := find(i)
		cnt[j][x]--
		if cnt[j][x] < 0 {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1905. 统计子岛屿

中等2 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵

题目、示例与约束

给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个岛屿是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。

如果 grid2 的一个岛屿，被 grid1 的一个岛屿完全包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。

请你返回 grid2 中 子岛屿 的数目。

示例 1：

输入：grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
输出：3
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。

示例 2：

输入：grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
输出：2 
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 2 个子岛屿。

提示：

m == grid1.length == grid2.length
n == grid1[i].length == grid2[i].length
1 <= m, n <= 500
grid1[i][j] 和 grid2[i][j] 都要么是 0 要么是 1 。

方法一：DFS · Go 实现

思考

对 $grid2$ 的每一座岛，需判断其全部陆地是否也落在 $grid1$ 的陆地上。若对每个格子单独比对而不连通，无法以岛为单位计数。

一次 DFS（或 BFS）即可遍历一座岛，并在遍历中把 $grid2$ 置零以免重复访问；同时用 $grid1$ 对应格是否为陆地把该岛标记为合法或非法。

对整张图扫描，每遇到 $grid2$ 中仍为 $1$ 的格子便启动一次搜索，返回值累加即为子岛屿个数。时间与格数成线性。

我们可以遍历矩阵 grid2 中的每一个格子 $(i, j)$ ，如果该格子为 $1$ ，则从该格子开始进行深度优先搜索，将与该格子相连的所有格子的值都置为 $0$ ，并记录与该格子相连的所有格子中，grid1 中对应格子的值是否为 $1$ ，如果为 $1$ ，则说明该格子在 grid1 中也是一个岛屿，否则不是。最后统计 grid2 中子岛屿的数量即可。

时间复杂度 $O (m \times n)$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别是矩阵 grid1 和 grid2 的行数和列数。

func countSubIslands(grid1 [][]int, grid2 [][]int) (ans int) {
	m, n := len(grid1), len(grid1[0])
	dirs := [5]int{-1, 0, 1, 0, -1}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		ok := grid1[i][j]
		grid2[i][j] = 0
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < m && y >= 0 && y < n && grid2[x][y] == 1 && dfs(x, y) == 0 {
				ok = 0
			}
		}
		return ok
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid2[i][j] == 1 {
				ans += dfs(i, j)
			}
		}
	}
	return
}

方法二：显式栈 · Go 实现

思考

$grid2$ 的一座岛是子岛屿，当且仅当其中每个陆地格在 $grid1$ 里也是陆地。格子若不按连通块归并，就无法按岛计数。

从一块陆地递归走向下一个邻居时，一条 $1000$ 格的蛇形岛就会超出递归上限，而 $m, n \leq 500$ 容得下这条蛇。

判定只要求走完整座岛，把 $grid2$ 置零，并把 $grid1$ 对应格按位与起来。这不依赖递归返回。

因此遇到仍为 $1$ 的格子就压入显式栈。弹出后与上 $grid1$ 的值，再把四个方向上的陆地标零并入栈。每次搜索的结果累加，就是子岛屿个数。

扫描 grid2 的每个格子。若它仍为 $1$ ，就用显式栈走完这座岛，沿途把 grid2 置为 $0$ ，并把 grid1 对应格按位与。结果为 $1$ 时这座岛是子岛屿。

时间复杂度 $O (m \times n)$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别是矩阵 grid1 和 grid2 的行数和列数。

func countSubIslands(grid1 [][]int, grid2 [][]int) (ans int) {
	m, n := len(grid1), len(grid1[0])
	dirs := [5]int{-1, 0, 1, 0, -1}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid2[i][j] != 1 {
				continue
			}
			ok := 1
			grid2[i][j] = 0
			stk := [][2]int{{i, j}}
			for len(stk) > 0 {
				cur := stk[len(stk)-1]
				stk = stk[:len(stk)-1]
				ok &= grid1[cur[0]][cur[1]]
				for k := 0; k < 4; k++ {
					x, y := cur[0]+dirs[k], cur[1]+dirs[k+1]
					if x >= 0 && x < m && y >= 0 && y < n && grid2[x][y] == 1 {
						grid2[x][y] = 0
						stk = append(stk, [2]int{x, y})
					}
				}
			}
			ans += ok
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1970. 你能穿过矩阵的最后一天

困难2 种解法

标签：深度优先搜索、广度优先搜索、并查集、数组、二分查找、矩阵

题目、示例与约束

给你一个下标从 1 开始的二进制矩阵，其中 0 表示陆地，1 表示水域。同时给你 row 和 col 分别表示矩阵中行和列的数目。

一开始在第 0 天，整个矩阵都是陆地。但每一天都会有一块新陆地被水淹没变成水域。给你一个下标从 1 开始的二维数组 cells ，其中 cells[i] = [r_i, c_i] 表示在第 i 天，第 r_i 行 c_i 列（下标都是从 1 开始）的陆地会变成水域（也就是 0 变成 1 ）。

你想知道从矩阵最上面一行走到最下面一行，且只经过陆地格子的 最后一天 是哪一天。你可以从最上面一行的任意格子出发，到达最下面一行的任意格子。你只能沿着四个基本方向移动（也就是上下左右）。

请返回只经过陆地格子能从最上面一行走到最下面一行的 最后一天 。

示例 1：

输入：row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
输出：2
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 2 天。

示例 2：

输入：row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
输出：1
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 1 天。

示例 3：

输入：row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
输出：3
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 3 天。

提示：

2 <= row, col <= 2 * 10⁴
4 <= row * col <= 2 * 10⁴
cells.length == row * col
1 <= r_i <= row
1 <= c_i <= col
cells 中的所有格子坐标都是唯一的。

方法一：二分查找 + BFS · Go 实现

思考

陆地逐日变成水域，能从首行走到末行的天数具有单调性：第 $k$ 天可行则更早也可行。 $m n$ 达 $2 \times 10^{4}$ ，可对天数二分再用 BFS 判定。

对中点 $k$ 把前 $k$ 格填成水，从第一行所有陆地出发四向扩展，能抵达最后一行则增大 $k$ 。

二分次数为对数，每次 BFS 线性于格子数。

我们注意到，如果我们能在第 $k$ 天从最上面一行走到最下面一行，那么对于任意 $0 < k^{'} < k$ ，我们也能在第 $k^{'}$ 天从最上面一行走到最下面一行。这存在着单调性，因此，我们可以使用二分查找，找到最大的 $k$ ，使得我们能在第 $k$ 天从最上面一行走到最下面一行。

我们定义二分查找的左边界 $l = 1$ ，右边界 $r = | c e l l s |$ ，其中 $| c e l l s |$ 表示数组 $c e l l s$ 的长度。然后，我们二分枚举 $k$ ，对于每一个 $k$ ，我们取 $cells$ 的前 $k$ 个元素，将这些元素对应的格子变成水域，然后使用广度优先搜索，从最上面一行开始，尝试走到最下面一行。如果我们能走到最下面一行，那么说明我们可以在第 $k$ 天从最上面一行走到最下面一行，我们就将左边界 $l$ 更新为 $k$ ，否则，我们将右边界 $r$ 更新为 $k - 1$ 。

时间复杂度 $O (m \times n \times \log (m \times n))$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别表示矩阵的行数和列数。

func latestDayToCross(row int, col int, cells [][]int) int {
	l, r := 1, len(cells)
	dirs := [5]int{-1, 0, 1, 0, -1}
	check := func(k int) bool {
		g := make([][]int, row)
		for i := range g {
			g[i] = make([]int, col)
		}
		for i := 0; i < k; i++ {
			g[cells[i][0]-1][cells[i][1]-1] = 1
		}
		q := [][2]int{}
		for j := 0; j < col; j++ {
			if g[0][j] == 0 {
				g[0][j] = 1
				q = append(q, [2]int{0, j})
			}
		}
		for len(q) > 0 {
			x, y := q[0][0], q[0][1]
			q = q[1:]
			if x == row-1 {
				return true
			}
			for i := 0; i < 4; i++ {
				nx, ny := x+dirs[i], y+dirs[i+1]
				if nx >= 0 && nx < row && ny >= 0 && ny < col && g[nx][ny] == 0 {
					g[nx][ny] = 1
					q = append(q, [2]int{nx, ny})
				}
			}
		}
		return false
	}
	for l < r {
		mid := (l + r + 1) >> 1
		if check(mid) {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return l
}

方法二：并查集 · Go 实现

思考

二分每次重建网格并搜索，常数偏大。倒序把水域变回陆地，用并查集把相邻陆地连通，并增设顶、底两个虚拟结点。

某天恢复后若顶底连通，则前一天仍可穿过，即为最晚日期。只需一次线性扫描。

我们可以先将所有的陆地格子初始化为 $1$ ，然后倒序遍历数组 $cells$ ，将每个格子对应的陆地格子变成 $0$ ，并将其与上下左右的陆地格子合并。我们还需要维护两个虚拟节点 $s$ 和 $t$ ，分别表示最上面一行和最下面一行的虚拟节点。如果 $s$ 和 $t$ 在并查集中连通，那么说明我们可以在第 $i$ 天从最上面一行走到最下面一行。

时间复杂度 $O (m \times n \times α (m \times n))$ ，空间复杂度 $O (m \times n)$ 。其中 $m$ 和 $n$ 分别表示矩阵的行数和列数，而 $α$ 表示 Ackermann 函数的反函数。

type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func latestDayToCross(row int, col int, cells [][]int) int {
	mn := len(cells)
	uf := newUnionFind(mn + 2)
	s, t := mn, mn+1
	g := make([][]int, row)
	for i := range g {
		g[i] = make([]int, col)
		for j := range g[i] {
			g[i][j] = 1
		}
	}
	dirs := [5]int{-1, 0, 1, 0, -1}
	for i := mn - 1; ; i-- {
		x, y := cells[i][0]-1, cells[i][1]-1
		g[x][y] = 0
		for j := 0; j < 4; j++ {
			nx, ny := x+dirs[j], y+dirs[j+1]
			if nx >= 0 && nx < row && ny >= 0 && ny < col && g[nx][ny] == 0 {
				uf.union(x*col+y, nx*col+ny)
			}
		}
		if x == 0 {
			uf.union(s, x*col+y)
		}
		if x == row-1 {
			uf.union(t, x*col+y)
		}
		if uf.find(s) == uf.find(t) {
			return i
		}
	}
}

力扣原题 · Doocs 题解来源

1971. 寻找图中是否存在路径

简单4 种解法

标签：深度优先搜索、广度优先搜索、并查集、图

题目、示例与约束

有一个具有 n 个顶点的双向图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [u_i, v_i] 表示顶点 ui 和顶点 vi 之间的双向边。每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。

给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，否则返回 false 。

示例 1：

输入：n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
输出：true
解释：存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2 
- 0 → 2

示例 2：

输入：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
输出：false
解释：不存在由顶点 0 到顶点 5 的路径.

提示：

1 <= n <= 2 * 10⁵
0 <= edges.length <= 2 * 10⁵
edges[i].length == 2
0 <= u_i, v_i <= n - 1
u_i != v_i
0 <= source, destination <= n - 1
不存在重复边
不存在指向顶点自身的边

方法一：DFS · Go 实现

思考

无向图上判断两点是否连通。建邻接表后 DFS，用访问集合避免环路，到达终点即成功。时间与点数边数线性。

我们首先将 $edges$ 转换成邻接表 $g$ ，然后使用 DFS，判断是否存在从 $source$ 到 $destination$ 的路径。

过程中，我们用数组 $vis$ 记录已经访问过的顶点，避免重复访问。

时间复杂度 $O (n + m)$ ，空间复杂度 $O (n + m)$ 。其中 $n$ 和 $m$ 分别是节点数和边数。

func validPath(n int, edges [][]int, source int, destination int) bool {
	vis := make([]bool, n)
	g := make([][]int, n)
	for _, e := range edges {
		u, v := e[0], e[1]
		g[u] = append(g[u], v)
		g[v] = append(g[v], u)
	}
	var dfs func(int) bool
	dfs = func(i int) bool {
		if i == destination {
			return true
		}
		vis[i] = true
		for _, j := range g[i] {
			if !vis[j] && dfs(j) {
				return true
			}
		}
		return false
	}
	return dfs(source)
}

方法二：BFS · Go 实现

思考

方法一用显式栈按深度优先扩展。队列按层扩展同样能判断连通：起点入队并标记，取出的点若是终点即成功，否则把未访问邻居入队。队列空则不可达。

我们也可以使用 BFS，判断是否存在从 $source$ 到 $destination$ 的路径。

具体地，我们定义一个队列 $q$ ，初始时将 $source$ 加入队列。另外，我们用一个集合 $vis$ 记录已经访问过的顶点，避免重复访问。

接下来，我们不断从队列中取出顶点 $i$ ，如果 $i = destination$ ，则说明存在从 $source$ 到 $destination$ 的路径，返回 $true$ 。否则，我们遍历 $i$ 的所有邻接顶点 $j$ ，如果 $j$ 没有被访问过，我们将 $j$ 加入队列 $q$ ，并且标记 $j$ 为已访问。

最后，如果队列为空，说明不存在从 $source$ 到 $destination$ 的路径，返回 $false$ 。

时间复杂度 $O (n + m)$ ，空间复杂度 $O (n + m)$ 。其中 $n$ 和 $m$ 分别是节点数和边数。

func validPath(n int, edges [][]int, source int, destination int) bool {
	g := make([][]int, n)
	for _, e := range edges {
		u, v := e[0], e[1]
		g[u] = append(g[u], v)
		g[v] = append(g[v], u)
	}
	q := []int{source}
	vis := make([]bool, n)
	vis[source] = true
	for len(q) > 0 {
		i := q[0]
		q = q[1:]
		if i == destination {
			return true
		}
		for _, j := range g[i] {
			if !vis[j] {
				vis[j] = true
				q = append(q, j)
			}
		}
	}
	return false
}

方法三：并查集 · Go 实现

思考

只需连通性、不要路径本身时，并查集把每条边两端合并，最后比较两点根是否相同。不必再在图上行走。

并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的合并及查询问题。它支持两种操作：

查找（Find）：确定某个元素处于哪个子集，单次操作时间复杂度 $O (α (n))$
合并（Union）：将两个子集合并成一个集合，单次操作时间复杂度 $O (α (n))$

对于本题，我们可以利用并查集，将 edges 中的边进行合并，然后判断 source 和 destination 是否在同一个集合中。

时间复杂度 $O (n \log n + m)$ 或 $O (n α (n) + m)$ ，空间复杂度 $O (n)$ 。其中 $n$ 和 $m$ 分别是节点数和边数。

type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func validPath(n int, edges [][]int, source int, destination int) bool {
	uf := newUnionFind(n)
	for _, e := range edges {
		uf.union(e[0], e[1])
	}
	return uf.find(source) == uf.find(destination)
}

方法四：显式栈 · Go 实现

思考

无向图上判断两点是否连通。 $n \leq 2 \times 10^{5}$ ，建邻接表后沿边扩展，用访问标记避免环路，到达终点即成功。时间与点数边数线性。

从起点递归进入邻居，链上的调用深度就是 $n$ ，会超出递归栈。是否连通与邻居的访问顺序无关。

因此改用显式栈。起点即终点时直接返回；否则入栈时标记，弹出后若邻居是终点则成功，只把未标记的邻居压入。栈空则不可达。

我们首先将 $edges$ 转换成邻接表 $g$ 。若 $source$ 就是 $destination$ ，直接返回 $true$ 。否则用显式栈从起点出发：入栈时把顶点记入 $vis$ ，弹出后若某个邻居是终点则返回 $true$ ，只把尚未标记的邻居压入栈。栈空则说明不存在路径。

时间复杂度 $O (n + m)$ ，空间复杂度 $O (n + m)$ 。其中 $n$ 和 $m$ 分别是节点数和边数。

func validPath(n int, edges [][]int, source int, destination int) bool {
	if source == destination {
		return true
	}
	g := make([][]int, n)
	for _, e := range edges {
		u, v := e[0], e[1]
		g[u] = append(g[u], v)
		g[v] = append(g[v], u)
	}
	vis := make([]bool, n)
	vis[source] = true
	stk := []int{source}
	for len(stk) > 0 {
		i := stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		for _, j := range g[i] {
			if j == destination {
				return true
			}
			if !vis[j] {
				vis[j] = true
				stk = append(stk, j)
			}
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

1998. 数组的最大公因数排序

困难1 种解法

标签：并查集、数组、数学、最大公约数、数论、排序、质因数分解、欧几里得算法

题目、示例与约束

给你一个整数数组 nums ，你可以在 nums 上执行下述操作 任意次 ：

如果 gcd(nums[i], nums[j]) > 1 ，交换 nums[i] 和 nums[j] 的位置。其中 gcd(nums[i], nums[j]) 是 nums[i] 和 nums[j] 的最大公因数。

如果能使用上述交换方式将 nums 按 非递减顺序 排列，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [7,21,3]
输出：true
解释：可以执行下述操作完成对 [7,21,3] 的排序：
- 交换 7 和 21 因为 gcd(7,21) = 7 。nums = [21,7,3]
- 交换 21 和 3 因为 gcd(21,3) = 3 。nums = [3,7,21]

示例 2：

输入：nums = [5,2,6,2]
输出：false
解释：无法完成排序，因为 5 不能与其他元素交换。

示例 3：

输入：nums = [10,5,9,3,15]
输出：true
解释：
可以执行下述操作完成对 [10,5,9,3,15] 的排序：
- 交换 10 和 15 因为 gcd(10,15) = 5 。nums = [15,5,9,3,10]
- 交换 15 和 3 因为 gcd(15,3) = 3 。nums = [3,5,9,15,10]
- 交换 10 和 15 因为 gcd(10,15) = 5 。nums = [3,5,9,10,15]

提示：

1 <= nums.length <= 3 * 10⁴
2 <= nums[i] <= 10⁵

方法一 · Go 实现

思考

若两数最大公因数大于 $1$ 则可交换，问能否排成非降序。传递闭包下，共享质因子的数属于同一可交换连通块。 $n$ 与值达 $10^{5}$ ，两两求 $gcd$ 不可行。

线性筛列出每个数的质因子，并查集把数值与其质因子合并。排序后若某位置的原值与目标值不在同一连通块，则无法换到该位。

var p []int

func gcdSort(nums []int) bool {
	n := 100010
	p = make([]int, n)
	for i := 0; i < n; i++ {
		p[i] = i
	}
	mx := 0
	for _, num := range nums {
		mx = max(mx, num)
	}
	f := make([][]int, mx+1)
	for i := 2; i <= mx; i++ {
		if len(f[i]) > 0 {
			continue
		}
		for j := i; j <= mx; j += i {
			f[j] = append(f[j], i)
		}
	}
	for _, i := range nums {
		for _, j := range f[i] {
			p[find(i)] = find(j)
		}
	}
	s := make([]int, len(nums))
	for i, num := range nums {
		s[i] = num
	}
	sort.Ints(s)
	for i, num := range nums {
		if s[i] != num && find(s[i]) != find(num) {
			return false
		}
	}
	return true
}

func find(x int) int {
	if p[x] != x {
		p[x] = find(p[x])
	}
	return p[x]
}

力扣原题 · Doocs 题解来源

2003. 每棵子树内缺失的最小基因值

困难2 种解法

标签：树、深度优先搜索、并查集、数组、动态规划

题目、示例与约束

有一棵根节点为 0 的 家族树 ，总共包含 n 个节点，节点编号为 0 到 n - 1 。给你一个下标从 0 开始的整数数组 parents ，其中 parents[i] 是节点 i 的父节点。由于节点 0 是根，所以 parents[0] == -1 。

总共有 10⁵ 个基因值，每个基因值都用 闭区间 [1, 10⁵] 中的一个整数表示。给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是节点 i 的基因值，且基因值 互不相同 。

请你返回一个数组 ans ，长度为 n ，其中 ans[i] 是以节点 i 为根的子树内缺失的最小基因值。

节点 x 为根的子树包含节点 x 和它所有的后代节点。

示例 1：

输入：parents = [-1,0,0,2], nums = [1,2,3,4]
输出：[5,1,1,1]
解释：每个子树答案计算结果如下：
- 0：子树包含节点 [0,1,2,3] ，基因值分别为 [1,2,3,4] 。5 是缺失的最小基因值。
- 1：子树只包含节点 1 ，基因值为 2 。1 是缺失的最小基因值。
- 2：子树包含节点 [2,3] ，基因值分别为 [3,4] 。1 是缺失的最小基因值。
- 3：子树只包含节点 3 ，基因值为 4 。1是缺失的最小基因值。

示例 2：

输入：parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
输出：[7,1,1,4,2,1]
解释：每个子树答案计算结果如下：
- 0：子树内包含节点 [0,1,2,3,4,5] ，基因值分别为 [5,4,6,2,1,3] 。7 是缺失的最小基因值。
- 1：子树内包含节点 [1,2] ，基因值分别为 [4,6] 。 1 是缺失的最小基因值。
- 2：子树内只包含节点 2 ，基因值为 6 。1 是缺失的最小基因值。
- 3：子树内包含节点 [3,4,5] ，基因值分别为 [2,1,3] 。4 是缺失的最小基因值。
- 4：子树内只包含节点 4 ，基因值为 1 。2 是缺失的最小基因值。
- 5：子树内只包含节点 5 ，基因值为 3 。1 是缺失的最小基因值。

示例 3：

输入：parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
输出：[1,1,1,1,1,1,1]
解释：所有子树都缺失基因值 1 。

提示：

n == parents.length == nums.length
2 <= n <= 10⁵
对于 i != 0 ，满足 0 <= parents[i] <= n - 1
parents[0] == -1
parents 表示一棵合法的树。
1 <= nums[i] <= 10⁵
nums[i] 互不相同。

方法一：DFS · Go 实现

思考

$n \leq 10^{5}$ ，对每个结点单独扫描子树会重复访问，总复杂度过高。基因值互不相同，因此 mex 大于 $1$ 的结点只能落在「含基因 $1$ 的结点到根」这条链上，其余结点答案恒为 $1$ 。

沿该链向上时，子树只会扩大：父结点的基因集合是当前子树再并上其余兄弟。已标记过的基因不必重扫。

为此自 $i d x$ 向根做 DFS，用 $h a s$ 累积出现过的基因， $i$ 单调递增找最小缺失值，并把结果写回 $a n s [i d x]$ 。

我们注意到，每个节点的基因值互不相同，因此，我们只需要找到基因值为 $1$ 的节点 $i d x$ ，那么除了从节点 $i d x$ 到根节点 $0$ 的每个节点，其它节点的答案都是 $1$ 。

因此，我们初始化答案数组 $a n s$ 为 $[1, 1, . . ., 1]$ ，然后我们的重点就在于求出节点 $i d x$ 到根节点 $0$ 的路径上的每个节点的答案。

我们可以从节点 $i d x$ 开始，通过深度优先搜索的方式，标记以 $i d x$ 作为根节点的子树中出现过的基因值，记录在数组 $h a s$ 中。搜索过程中，我们用一个数组 $v i s$ 标记已经访问过的节点，防止重复访问。

接下来，我们从 $i = 2$ 开始，不断向后寻找第一个没有出现过的基因值，即为节点 $i d x$ 的答案。这里 $i$ 是严格递增的，因为基因值互不相同，所以我们一定能在 $[1, . . n + 1]$ 中找到一个没有出现过的基因值。

然后，我们更新节点 $i d x$ 的答案，即 $a n s [i d x] = i$ ，并将 $i d x$ 更新为其父节点，继续上述过程，直到 $i d x = - 1$ ，即到达了根节点 $0$ 。

最后，我们返回答案数组 $a n s$ 即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是节点的数量。

func smallestMissingValueSubtree(parents []int, nums []int) []int {
	n := len(nums)
	g := make([][]int, n)
	vis := make([]bool, n)
	has := make([]bool, n+2)
	idx := -1
	ans := make([]int, n)
	for i, p := range parents {
		if i > 0 {
			g[p] = append(g[p], i)
		}
		if nums[i] == 1 {
			idx = i
		}
		ans[i] = 1
	}
	if idx < 0 {
		return ans
	}
	var dfs func(int)
	dfs = func(i int) {
		if vis[i] {
			return
		}
		vis[i] = true
		if nums[i] < len(has) {
			has[nums[i]] = true
		}
		for _, j := range g[i] {
			dfs(j)
		}
	}
	for i := 2; idx != -1; idx = parents[idx] {
		dfs(idx)
		for has[i] {
			i++
		}
		ans[idx] = i
	}
	return ans
}

方法二：显式栈 · Go 实现

思考

$n \leq 10^{5}$ ，对每个结点单独扫描子树会重复访问，总复杂度过高。基因值互不相同，因此 mex 大于 $1$ 的结点只能落在「含基因 $1$ 的结点到根」这条链上，其余结点答案恒为 $1$ 。若基因 $1$ 在根上，而树是一条链，递归标记整棵子树的深度就是 $n$ ，会超出递归栈。

沿该链向上时，子树只会扩大：父结点的基因集合是当前子树再并上其余兄弟。已标记过的基因不必重扫。

显式栈自 $i d x$ 向根标记子树，用 $h a s$ 累积出现过的基因， $i$ 单调递增找最小缺失值，并把结果写回 $a n s [i d x]$ 。

因此，我们初始化答案数组 $a n s$ 为 $[1, 1, . . ., 1]$ ，然后我们的重点就在于求出节点 $i d x$ 到根节点 $0$ 的路径上的每个节点的答案。

我们可以从节点 $i d x$ 开始，用显式栈标记以 $i d x$ 作为根节点的子树中出现过的基因值，记录在数组 $h a s$ 中。遍历过程中，我们用一个数组 $v i s$ 标记已经访问过的节点，防止重复访问。

然后，我们更新节点 $i d x$ 的答案，即 $a n s [i d x] = i$ ，并将 $i d x$ 更新为其父节点，继续上述过程，直到 $i d x = - 1$ ，即到达了根节点 $0$ 。

最后，我们返回答案数组 $a n s$ 即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是节点的数量。

func smallestMissingValueSubtree(parents []int, nums []int) []int {
	n := len(nums)
	g := make([][]int, n)
	idx := -1
	ans := make([]int, n)
	for i, p := range parents {
		if i > 0 {
			g[p] = append(g[p], i)
		}
		if nums[i] == 1 {
			idx = i
		}
		ans[i] = 1
	}
	if idx < 0 {
		return ans
	}
	vis := make([]bool, n)
	has := make([]bool, n+2)
	dfs := func(start int) {
		stk := []int{start}
		for len(stk) > 0 {
			i := stk[len(stk)-1]
			stk = stk[:len(stk)-1]
			if vis[i] {
				continue
			}
			vis[i] = true
			if nums[i] < len(has) {
				has[nums[i]] = true
			}
			for _, j := range g[i] {
				stk = append(stk, j)
			}
		}
	}
	for i := 2; idx != -1; idx = parents[idx] {
		dfs(idx)
		for has[i] {
			i++
		}
		ans[idx] = i
	}
	return ans
}

力扣原题 · Doocs 题解来源

2076. 处理含限制条件的好友请求

困难1 种解法

标签：并查集、图

题目、示例与约束

给你一个整数 n ，表示网络上的用户数目。每个用户按从 0 到 n - 1 进行编号。

给你一个下标从 0 开始的二维整数数组 restrictions ，其中 restrictions[i] = [x_i, y_i] 意味着用户 x_i 和用户 y_i 不能成为朋友，不管是直接还是通过其他用户间接。

最初，用户里没有人是其他用户的朋友。给你一个下标从 0 开始的二维整数数组 requests 表示好友请求的列表，其中 requests[j] = [u_j, v_j] 是用户 u_j 和用户 v_j 之间的一条好友请求。

如果 u_j 和 v_j 可以成为朋友，那么好友请求将会成功。每个好友请求都会按列表中给出的顺序进行处理（即，requests[j] 会在 requests[j + 1] 前）。一旦请求成功，那么对所有未来的好友请求而言， u_j 和 v_j 将会 成为直接朋友。

返回一个 布尔数组 result ，其中元素遵循此规则：如果第 j 个好友请求成功，那么 result[j] 就是 true ；否则，为 false 。

注意：如果 u_j 和 v_j 已经是直接朋友，那么他们之间的请求将仍然成功。

示例 1：

输入：n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]
输出：[true,false]
解释：
请求 0 ：用户 0 和 用户 2 可以成为朋友，所以他们成为直接朋友。 
请求 1 ：用户 2 和 用户 1 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (1--2--0) 。

示例 2：

输入：n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]]
输出：[true,false]
解释：
请求 0 ：用户 1 和 用户 2 可以成为朋友，所以他们成为直接朋友。 
请求 1 ：用户 0 和 用户 2 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (0--2--1) 。

示例 3：

输入：n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]
输出：[true,false,true,false]
解释：
请求 0 ：用户 0 和 用户 4 可以成为朋友，所以他们成为直接朋友。 
请求 1 ：用户 1 和 用户 2 不能成为朋友，因为他们之间存在限制。
请求 2 ：用户 3 和 用户 1 可以成为朋友，所以他们成为直接朋友。 
请求 3 ：用户 3 和 用户 4 不能成为朋友，因为这会使 用户 0 和 用户 1 成为间接朋友 (0--4--3--1) 。

提示：

2 <= n <= 1000
0 <= restrictions.length <= 1000
restrictions[i].length == 2
0 <= x_i, y_i <= n - 1
x_i != y_i
1 <= requests.length <= 1000
requests[j].length == 2
0 <= u_j, v_j <= n - 1
u_j != v_j

方法一：并查集 · Go 实现

思考

请求须按顺序处理，且限制是「两类人不能同属一个朋友圈」。并查集维护当前连通性。 $q, m, n \leq 1000$ ，每个请求可扫描全部限制。

已在同一集合则直接成功；否则若某条限制的两端分别与 $u, v$ 同组，则拒绝，成功才合并。路径压缩保证查找近常数。

我们可以用并查集来维护朋友关系，然后对于每个请求，判断是否满足限制条件。

对于当前请求的两个人 $(u, v)$ ，如果他们已经是朋友，那么可以直接接受请求；否则，我们遍历限制条件，如果存在限制条件 $(x, y)$ ，使得 $u$ 和 $x$ 互为朋友并且 $v$ 和 $y$ 互为朋友，或者 $u$ 和 $y$ 互为朋友并且 $v$ 和 $x$ 互为朋友，那么就不能接受请求。

时间复杂度 $O (q \times m \times \log (n))$ ，空间复杂度 $O (n)$ 。其中 $q$ 和 $m$ 分别是请求的数量和限制条件的数量。

func friendRequests(n int, restrictions [][]int, requests [][]int) (ans []bool) {
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, req := range requests {
		pu, pv := find(req[0]), find(req[1])
		if pu == pv {
			ans = append(ans, true)
		} else {
			ok := true
			for _, r := range restrictions {
				px, py := find(r[0]), find(r[1])
				if px == pu && py == pv || px == pv && py == pu {
					ok = false
					break
				}
			}
			ans = append(ans, ok)
			if ok {
				p[pv] = pu
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2092. 找出知晓秘密的所有专家

困难1 种解法

标签：深度优先搜索、广度优先搜索、并查集、图、排序

题目、示例与约束

给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号。另外给你一个下标从 0 开始的二维整数数组 meetings ，其中 meetings[i] = [x_i, y_i, time_i] 表示专家 x_i 和专家 y_i 在时间 time_i 要开一场会。一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson 。

专家 0 有一个秘密，最初，他在时间 0 将这个秘密分享给了专家 firstPerson 。接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。更正式的表达是，每次会议，如果专家 x_i 在时间 time_i 时知晓这个秘密，那么他将会与专家 y_i 分享这个秘密，反之亦然。

秘密共享是 瞬时发生 的。也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享。

在所有会议都结束之后，返回所有知晓这个秘密的专家列表。你可以按 任何顺序 返回答案。

示例 1：

输入：n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
输出：[0,1,2,3,5]
解释：
时间 0 ，专家 0 将秘密与专家 1 共享。
时间 5 ，专家 1 将秘密与专家 2 共享。
时间 8 ，专家 2 将秘密与专家 3 共享。
时间 10 ，专家 1 将秘密与专家 5 共享。
因此，在所有会议结束后，专家 0、1、2、3 和 5 都将知晓这个秘密。

示例 2：

输入：n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
输出：[0,1,3]
解释：
时间 0 ，专家 0 将秘密与专家 3 共享。
时间 2 ，专家 1 与专家 2 都不知晓这个秘密。
时间 3 ，专家 3 将秘密与专家 0 和专家 1 共享。
因此，在所有会议结束后，专家 0、1 和 3 都将知晓这个秘密。

示例 3：

输入：n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
输出：[0,1,2,3,4]
解释：
时间 0 ，专家 0 将秘密与专家 1 共享。
时间 1 ，专家 1 将秘密与专家 2 共享，专家 2 将秘密与专家 3 共享。
注意，专家 2 可以在收到秘密的同一时间分享此秘密。
时间 2 ，专家 3 将秘密与专家 4 共享。
因此，在所有会议结束后，专家 0、1、2、3 和 4 都将知晓这个秘密。

提示：

2 <= n <= 10⁵
1 <= meetings.length <= 10⁵
meetings[i].length == 3
0 <= x_i, y_i<= n - 1
x_i != y_i
1 <= time_i <= 10⁵
1 <= firstPerson <= n - 1

方法一：模拟 + 图遍历 · Go 实现

思考

秘密只在同一时刻的会议上沿连通块传播， $n$ 与会议数均为 $10^{5}$ 。按时间排序后，同一时刻的边构成一张临时图，只从已经知情的人 BFS。

不同时刻互不影响：本时刻传播结束才进入下一时刻。vis 一旦为真则永久知情。

本题的核心思路是通过模拟会议的传播过程来找出所有最终会知道秘密的人。我们可以将每次会议视为一个无向图的边，其中每个参与者是图中的一个节点，会议的时间是节点之间连接的边的“时间戳”。在每个时间点，我们遍历所有会议，利用广度优先搜索（BFS）来模拟秘密的传播。

创建一个布尔数组 $vis$ 来记录每个人是否知道秘密。初始时， $vis [0] = true$ 和 $vis [firstPerson] = true$ ，表示0号和 $firstPerson$ 已经知道秘密。

我们首先按照每个会议的时间进行排序，以确保每次遍历时能够按照正确的顺序处理会议。

接下来，处理每一组相同时间的会议。对于每一组相同时间的会议（即 $meetings [i] [2] = meetings [i + 1] [2]$ ），我们将它们视为同一时刻发生的事件。对于每个会议，记录参与者的关系，并将这些参与者加入一个集合中。

然后，我们利用 BFS 来传播秘密。对于当前时间点的所有参与者，如果其中有任何人已经知道秘密，我们将通过 BFS 遍历该参与者的相邻节点（即会议中的其他参与者），将他们标记为知道秘密。这个过程会继续传播，直到所有在这次会议中能够知道秘密的人都被更新。

当所有会议处理完毕后，遍历 $vis$ 数组，将所有知道秘密的人的编号加入结果列表并返回。

时间复杂度 $O (m \times \log m + n)$ ，空间复杂度 $O (n)$ 。其中 $m$ 和 $n$ 分别是会议数量和专家数量。

func findAllPeople(n int, meetings [][]int, firstPerson int) []int {
	vis := make([]bool, n)
	vis[0], vis[firstPerson] = true, true
	sort.Slice(meetings, func(i, j int) bool {
		return meetings[i][2] < meetings[j][2]
	})
	for i, j, m := 0, 0, len(meetings); i < m; i = j + 1 {
		j = i
		for j+1 < m && meetings[j+1][2] == meetings[i][2] {
			j++
		}
		g := map[int][]int{}
		s := map[int]bool{}
		for _, e := range meetings[i : j+1] {
			x, y := e[0], e[1]
			g[x] = append(g[x], y)
			g[y] = append(g[y], x)
			s[x], s[y] = true, true
		}
		q := []int{}
		for u := range s {
			if vis[u] {
				q = append(q, u)
			}
		}
		for len(q) > 0 {
			u := q[0]
			q = q[1:]
			for _, v := range g[u] {
				if !vis[v] {
					vis[v] = true
					q = append(q, v)
				}
			}
		}
	}
	var ans []int
	for i, v := range vis {
		if v {
			ans = append(ans, i)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2157. 字符串分组

困难1 种解法

标签：位运算、并查集、数组、哈希表、字符串

题目、示例与约束

给你一个下标从 0 开始的字符串数组 words 。每个字符串都只包含 小写英文字母 。words 中任意一个子串中，每个字母都至多只出现一次。

如果通过以下操作之一，我们可以从 s1 的字母集合得到 s2 的字母集合，那么我们称这两个字符串为 关联的 ：

往 s1 的字母集合中添加一个字母。
从 s1 的字母集合中删去一个字母。
将 s1 中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。

数组 words 可以分为一个或者多个无交集的组。如果一个字符串与另一个字符串关联，那么它们应当属于同一个组。

注意，你需要确保分好组后，一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下，分组方案是唯一的。

请你返回一个长度为 2 的数组 ans ：

ans[0] 是 words 分组后的 总组数 。
ans[1] 是字符串数目最多的组所包含的字符串数目。

示例 1：

输入：words = ["a","b","ab","cde"]
输出：[2,3]
解释：
- words[0] 可以得到 words[1] （将 'a' 替换为 'b'）和 words[2] （添加 'b'）。所以 words[0] 与 words[1] 和 words[2] 关联。
- words[1] 可以得到 words[0] （将 'b' 替换为 'a'）和 words[2] （添加 'a'）。所以 words[1] 与 words[0] 和 words[2] 关联。
- words[2] 可以得到 words[0] （删去 'b'）和 words[1] （删去 'a'）。所以 words[2] 与 words[0] 和 words[1] 关联。
- words[3] 与 words 中其他字符串都不关联。
所以，words 可以分成 2 个组 ["a","b","ab"] 和 ["cde"] 。最大的组大小为 3 。

示例 2：

输入：words = ["a","ab","abc"]
输出：[1,3]
解释：
- words[0] 与 words[1] 关联。
- words[1] 与 words[0] 和 words[2] 关联。
- words[2] 与 words[1] 关联。
由于所有字符串与其他字符串都关联，所以它们全部在同一个组内。
所以最大的组大小为 3 。

提示：

1 <= words.length <= 2 * 10⁴
1 <= words[i].length <= 26
words[i] 只包含小写英文字母。
words[i] 中每个字母最多只出现一次。

方法一：状态压缩（位运算） + 并查集 · Go 实现

思考

两个单词若能通过加、删或替换一个字母互相得到，则属于同一组。单词可看成 $26$ 位掩码，枚举邻居若按字符串比较则过慢。 $n \leq 2 \times 10^{4}$ ，需把掩码放进并查集。

每个掩码与「翻转一位」（加或删）以及「先删一位再加另一位」（替换）的掩码合并。相同掩码本身已是一组，计入该组大小。

扫描全部已出现掩码做合并，维护连通块个数与最大块大小。

func groupStrings(words []string) []int {
	p := map[int]int{}
	size := map[int]int{}
	mx, n := 0, len(words)
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	union := func(a, b int) {
		if _, ok := p[b]; !ok {
			return
		}
		pa, pb := find(a), find(b)
		if pa == pb {
			return
		}
		p[pa] = pb
		size[pb] += size[pa]
		mx = max(mx, size[pb])
		n--
	}

	for _, word := range words {
		x := 0
		for _, c := range word {
			x |= 1 << (c - 'a')
		}
		p[x] = x
		size[x]++
		mx = max(mx, size[x])
		if size[x] > 1 {
			n--
		}
	}
	for x := range p {
		for i := 0; i < 26; i++ {
			union(x, x^(1<<i))
			if ((x >> i) & 1) != 0 {
				for j := 0; j < 26; j++ {
					if ((x >> j) & 1) == 0 {
						union(x, x^(1<<i)|(1<<j))
					}
				}
			}
		}
	}
	return []int{n, mx}
}

力扣原题 · Doocs 题解来源

2307. 检查方程中的矛盾之处 🔒

困难1 种解法

标签：深度优先搜索、并查集、图、数组、字符串

题目、示例与约束

给你一个由字符串二维数组 equations 和实数数组 values ，其中 equations[i] = [A_i, B_i]，values[i] 表示 A_i / B_i = values[i].。

确定方程中是否存在矛盾。如果存在矛盾则返回 true，否则返回 false。

注意:

当检查两个数字是否相等时，检查它们的 绝对差值 是否小于 10^-5.
生成的测试用例没有针对精度的用例，即使用 double 就足以解决问题。

示例 1:

输入: equations = [["a","b"],["b","c"],["a","c"]], values = [3,0.5,1.5]
输出: false
解释:
给定的方程为: a / b = 3, b / c = 0.5, a / c = 1.5
方程中没有矛盾。满足所有方程的一个可能的分配是:
a = 3, b = 1 和 c = 2.

示例 2:

输入: equations = [["le","et"],["le","code"],["code","et"]], values = [2,5,0.5]
输出: true
解释:
给定的方程为: le / et = 2, le / code = 5, code / et = 0.5
根据前两个方程，我们得到 code / et = 0.4.
因为第三个方程是 code / et = 0.5, 所以矛盾。

提示:

1 <= equations.length <= 100
equations[i].length == 2
1 <= A_i.length, B_i.length <= 5
A_i, B_i 由小写英文字母组成。
equations.length == values.length
0.0 < values[i] <= 10.0
values[i] 小数点后最多 2 位。

方法一：带权并查集 · Go 实现

思考

每个等式给出两个变量的比值。若沿不同路径把同一对变量连起来，比值可能冲突。变量至多两百个，等式至多 $100$ 条，适合并查集维护连通关系。

将变量映射为整数后，用权值 $w [x]$ 表示 $x$ 到根的比值。合并时按乘法更新权；若两点已在同一集合，则用路径压缩后的权检验 $v \cdot w [a]$ 是否与 $w [b]$ 在误差内一致。出现偏差即存在矛盾。

我们先将字符串转换成从 $0$ 开始的整数，然后遍历所有的等式，将等式中的两个字符串映射成对应的整数 $a$ 和 $b$ ，如果这两个整数不在同一个集合中，就将它们合并到同一个集合中，并且记录下两个整数的权值，即 $a$ 与 $b$ 的比值。如果这两个整数在同一个集合中，就判断它们的权值是否满足等式，如果不满足就返回 true。

时间复杂度 $O (n \times \log n)$ 或 $O (n \times α (n))$ ，空间复杂度 $O (n)$ 。其中 $n$ 是等式的数量。

相似题目：

399. 除法求值

func checkContradictions(equations [][]string, values []float64) bool {
	d := make(map[string]int)
	n := 0

	for _, e := range equations {
		for _, s := range e {
			if _, ok := d[s]; !ok {
				d[s] = n
				n++
			}
		}
	}

	p := make([]int, n)
	for i := range p {
		p[i] = i
	}

	w := make([]float64, n)
	for i := range w {
		w[i] = 1.0
	}

	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			root := find(p[x])
			w[x] *= w[p[x]]
			p[x] = root
		}
		return p[x]
	}
	for i, e := range equations {
		a, b := d[e[0]], d[e[1]]
		v := values[i]

		pa, pb := find(a), find(b)
		if pa != pb {
			p[pb] = pa
			w[pb] = v * w[a] / w[b]
		} else if v*w[a]-w[b] >= 1e-5 || w[b]-v*w[a] >= 1e-5 {
			return true
		}
	}

	return false
}

力扣原题 · Doocs 题解来源

LeetCode Go · 并查集（2） ​

1101. 彼此熟识的最早时间 🔒 ​

1102. 得分最高的路径 🔒 ​

1135. 最低成本连通所有城市 🔒 ​

1168. 水资源分配优化 🔒 ​

1202. 交换字符串中的元素 ​

1254. 统计封闭岛屿的数目 ​

1258. 近义词句子 🔒 ​

1267. 统计参与通信的服务器 ​

1319. 连通网络的操作次数 ​

1361. 验证二叉树 ​

1391. 检查网格中是否存在有效路径 ​

1489. 找到最小生成树里的关键边和伪关键边 ​

1559. 二维网格图中探测环 ​

1569. 将子数组重新排序得到同一个二叉搜索树的方案数 ​

1579. 保证图可完全遍历 ​

1584. 连接所有点的最小费用 ​

1627. 带阈值的图连通性 ​

1631. 最小体力消耗路径 ​

1632. 矩阵转换后的排名 ​

1697. 检查边长度限制的路径是否存在 ​

1722. 执行交换操作后的最小汉明距离 ​

1905. 统计子岛屿 ​

1970. 你能穿过矩阵的最后一天 ​

1971. 寻找图中是否存在路径 ​

1998. 数组的最大公因数排序 ​

2003. 每棵子树内缺失的最小基因值 ​

2076. 处理含限制条件的好友请求 ​

2092. 找出知晓秘密的所有专家 ​

2157. 字符串分组 ​

2307. 检查方程中的矛盾之处 🔒 ​

继续阅读

LeetCode Go · 并查集（2）

1101. 彼此熟识的最早时间 🔒

1102. 得分最高的路径 🔒

1135. 最低成本连通所有城市 🔒

1168. 水资源分配优化 🔒

1202. 交换字符串中的元素

1254. 统计封闭岛屿的数目

1258. 近义词句子 🔒

1267. 统计参与通信的服务器

1319. 连通网络的操作次数

1361. 验证二叉树

1391. 检查网格中是否存在有效路径

1489. 找到最小生成树里的关键边和伪关键边

1559. 二维网格图中探测环

1569. 将子数组重新排序得到同一个二叉搜索树的方案数

1579. 保证图可完全遍历

1584. 连接所有点的最小费用

1627. 带阈值的图连通性

1631. 最小体力消耗路径

1632. 矩阵转换后的排名

1697. 检查边长度限制的路径是否存在

1722. 执行交换操作后的最小汉明距离

1905. 统计子岛屿

1970. 你能穿过矩阵的最后一天

1971. 寻找图中是否存在路径

1998. 数组的最大公因数排序

2003. 每棵子树内缺失的最小基因值

2076. 处理含限制条件的好友请求

2092. 找出知晓秘密的所有专家

2157. 字符串分组

2307. 检查方程中的矛盾之处 🔒