LeetCode Go · 图与最短路径（3）

返回题库与筛选 · 收录范围与使用说明

来源与许可

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

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

2065. 最大化一张图中的路径价值

困难1 种解法

标签：图、数组、回溯

题目、示例与约束

给你一张 无向 图，图中有 n 个节点，节点编号从 0 到 n - 1 （都包括）。同时给你一个下标从 0 开始的整数数组 values ，其中 values[i] 是第 i 个节点的 价值 。同时给你一个下标从 0 开始的二维整数数组 edges ，其中 edges[j] = [uj, vj, timej] 表示节点 uj 和 vj 之间有一条需要 timej 秒才能通过的无向边。最后，给你一个整数 maxTime 。

合法路径 指的是图中任意一条从节点 0 开始，最终回到节点 0 ，且花费的总时间 不超过 maxTime 秒的一条路径。你可以访问一个节点任意次。一条合法路径的 价值 定义为路径中 不同节点 的价值 之和 （每个节点的价值 至多 算入价值总和中一次）。

请你返回一条合法路径的 最大 价值。

注意：每个节点 至多 有 四条 边与之相连。

 

示例 1：

输入：values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49
输出：75
解释：
一条可能的路径为：0 -> 1 -> 0 -> 3 -> 0 。总花费时间为 10 + 10 + 10 + 10 = 40 <= 49 。
访问过的节点为 0 ，1 和 3 ，最大路径价值为 0 + 32 + 43 = 75 。

示例 2：

输入：values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30
输出：25
解释：
一条可能的路径为：0 -> 3 -> 0 。总花费时间为 10 + 10 = 20 <= 30 。
访问过的节点为 0 和 3 ，最大路径价值为 5 + 20 = 25 。

示例 3：

输入：values = [1,2,3,4], edges = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]], maxTime = 50
输出：7
解释：
一条可能的路径为：0 -> 1 -> 3 -> 1 -> 0 。总花费时间为 10 + 13 + 13 + 10 = 46 <= 50 。
访问过的节点为 0 ，1 和 3 ，最大路径价值为 1 + 2 + 4 = 7 。

示例 4：

输入：values = [0,1,2], edges = [[1,2,10]], maxTime = 10
输出：0
解释：
唯一一条路径为 0 。总花费时间为 0 。
唯一访问过的节点为 0 ，最大路径价值为 0 。

 

提示：

• n == values.length
• 1 <= n <= 1000
• 0 <= values[i] <= 108
• 0 <= edges.length <= 2000
• edges[j].length == 3
• 0 <= uj < vj <= n - 1
• 10 <= timej, maxTime <= 100
• [uj, vj] 所有节点对 互不相同 。
• 每个节点 至多有四条 边。
• 图可能不连通。

方法一：DFS · Go 实现

思考

$maxTime\le 100$ 且边权 $\ge 10$，从 $0$ 出发的路径至多约 $10$ 条边；度数 $\le 4$，搜索树有限。价值只在结点首次访问时计入，允许重复走边。

DFS 记录当前点、已用时间与累计价值，回到 $0$ 时更新答案。vis 在进入新点时置位、回溯时清除，重复访问不再加分。

我们观察题目的数据范围，可以发现从 $0$ 开始的每条合法路径的边数不超过 $\frac{\mathit{\text{maxTime}}}{min(tim{e}_j)}=\frac{100}{10}=10$ 条，并且每个节点至多有四条边，所以我们可以直接使用朴素的 DFS 暴力搜索所有合法路径。

我们先将图的边存储在邻接表表 $g$ 中，然后我们设计一个函数 $\mathit{\text{dfs}}(u,\mathit{\text{cost}},\mathit{\text{value}})$，其中 $u$ 表示当前节点编号，而 $\mathit{\text{cost}}$ 和 $\mathit{\text{value}}$ 分别表示当前路径的花费时间和价值。另外，使用一个长度为 $n$ 的数组 $\mathit{\text{vis}}$ 记录每个节点是否被访问过。初始时，我们将节点 $0$ 标记为已访问。

函数 $\mathit{\text{dfs}}(u,\mathit{\text{cost}},\mathit{\text{value}})$ 的逻辑如下：

• 如果当前节点编号 $u$ 等于 $0$，表示我们已经回到了起点，那么我们更新答案为 $max(\mathit{\text{ans}},\mathit{\text{value}})$；
• 遍历当前节点 $u$ 的所有邻居节点 $v$，如果当前路径的花费时间加上边 $(u,v)$ 的时间 $t$ 不超过 $\mathit{\text{maxTime}}$，那么我们可以选择继续访问节点 $v$；
  • 如果节点 $v$ 已经被访问过，那么我们直接递归调用 $\mathit{\text{dfs}}(v,\mathit{\text{cost}}+t,\mathit{\text{value}})$；
  • 如果节点 $v$ 没有被访问过，我们标记节点 $v$ 为已访问，然后递归调用 $\mathit{\text{dfs}}(v,\mathit{\text{cost}}+t,\mathit{\text{value}}+\mathit{\text{values}}[v])$，最后恢复节点 $v$ 的访问状态。

在主函数中，我们调用 $\mathit{\text{dfs}}(0,0,\mathit{\text{values}}[0])$，并返回答案 $\mathit{\text{ans}}$ 即可。

时间复杂度 $O(n+m+4^{\frac{\mathit{\text{maxTime}}}{min(tim{e}_j)}})$，空间复杂度 $O(n+m+\frac{\mathit{\text{maxTime}}}{min(tim{e}_j)})$。其中 $n$ 和 $m$ 分别表示节点数和边数。

func maximalPathQuality(values []int, edges [][]int, maxTime int) (ans int) {
	n := len(values)
	g := make([][][2]int, n)
	for _, e := range edges {
		u, v, t := e[0], e[1], e[2]
		g[u] = append(g[u], [2]int{v, t})
		g[v] = append(g[v], [2]int{u, t})
	}
	vis := make([]bool, n)
	vis[0] = true
	var dfs func(u, cost, value int)
	dfs = func(u, cost, value int) {
		if u == 0 {
			ans = max(ans, value)
		}
		for _, e := range g[u] {
			v, t := e[0], e[1]
			if cost+t <= maxTime {
				if vis[v] {
					dfs(v, cost+t, value)
				} else {
					vis[v] = true
					dfs(v, cost+t, value+values[v])
					vis[v] = false
				}
			}
		}
	}
	dfs(0, 0, values[0])
	return
}

力扣原题 · Doocs 题解来源

2077. 殊途同归 🔒

中等1 种解法

标签：图

题目、示例与约束

迷宫由 n 个从 1 到 n 的房间组成，有些房间由走廊连接。给定一个二维整数数组 corridors，其中 corridors[i] = [room1i, room2i] 表示有一条走廊连接 room1i 和room2i，允许迷宫中的一个人从 room1i 到 room2i ，反之亦然。

迷宫的设计者想知道迷宫有多让人困惑。迷宫的 混乱分数 是 长度为 3 的不同的环的数量。

• 例如, 1 → 2 → 3 → 1 是长度为 3 的环, 但 1 → 2 → 3 → 4 和 1 → 2 → 3 → 2 → 1 不是。

如果在第一个环中访问的一个或多个房间 不在 第二个环中，则认为两个环是 不同 的。

返回迷宫的混乱分数。

示例 1:

输入: n = 5, corridors = [[1,2],[5,2],[4,1],[2,4],[3,1],[3,4]]
输出: 2
解释:
一个长度为 3 的环为 4→1→3→4，用红色表示。
注意，这是与 3→4→1→3 或 1→3→4→1 相同的环，因为房间是相同的。
另一个长度为 3 的环为 1→2→4→1，用蓝色表示。
因此，有两个长度为 3 的不同的环。

示例 2:

输入: n = 4, corridors = [[1,2],[3,4]]
输出: 0
解释:
没有长度为 3 的环。

 

提示:

• 2 <= n <= 1000
• 1 <= corridors.length <= 5 * 104
• corridors[i].length == 2
• 1 <= room1i, room2i <= n
• room1i != room2i

• 没有重复的走廊。

方法一：哈希表 · Go 实现

思考

要数长度为 $3$ 的环。走廊给出无向边，邻接用集合存储以便 $O(1)$ 判边。对每个点枚举其邻居的无序对，若该对也相邻则构成三角形。

每个环被三个顶点各计一次，答案除以 $3$。

长度为 3 的环，由三个顶点、三条边组成。我们假设三个顶点分别为 a, b, c。

那么一定存在 c <=> a，c <=> b 以及 a <=> b，即环中的每个点都与其他两点直接相连。我们可以用哈希表来存放每个点的相邻点。

由于环的长度为 3，每个相同的环会被重复统计 3 次，因此答案需除以 3。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

func numberOfPaths(n int, corridors [][]int) int {
	g := make([]map[int]bool, n+1)
	for i := range g {
		g[i] = make(map[int]bool)
	}
	for _, c := range corridors {
		a, b := c[0], c[1]
		g[a][b] = true
		g[b][a] = true
	}
	ans := 0
	for c := 1; c <= n; c++ {
		nxt := []int{}
		for v := range g[c] {
			nxt = append(nxt, v)
		}
		m := len(nxt)
		for i := 0; i < m; i++ {
			for j := i + 1; j < m; j++ {
				a, b := nxt[i], nxt[j]
				if g[b][a] {
					ans++
				}
			}
		}
	}
	return ans / 3
}

力扣原题 · Doocs 题解来源

2093. 前往目标城市的最小费用 🔒

中等1 种解法

标签：图、最短路、Dijkstra 算法、堆（优先队列）

题目、示例与约束

一组公路连接 n 个城市，城市编号为从 0 到 n - 1 。 输入包含一个二维数组 highways ，其中 highways[i] = [city1i, city2i, tolli] 表示有一条连接城市 city1i 和 city2i 的双向公路，允许汽车缴纳值为 tolli 的费用从  city1i 前往 city2i 或 从  city2i 前往 city1i 。

另给你一个整数 discounts 表示你最多可以使用折扣的次数。你可以使用一次折扣使通过第 ith 条公路的费用降低至 tolli / 2（向下取整）。 最多只可使用 discounts 次折扣， 且 每条公路最多只可使用一次折扣 。

返回从城市0 前往城市 n - 1 的 最小费用 。如果不存在从城市0 前往城市 n - 1 的路径，返回 -1 。

 

示例 1：

输入：n = 5, highways = [[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]], discounts = 1
输出：9
解释：
从 0 前往 1 ，需要费用为 4 。
从 1 前往 4 并使用一次折扣，需要费用为 11 / 2 = 5 。
从 0 前往 4 最小费用为 4 + 5 = 9 。

示例 2：

输入：n = 4, highways = [[1,3,17],[1,2,7],[3,2,5],[0,1,6],[3,0,20]], discounts = 20
输出：8
解释：
从 0 前往 1 并使用一次折扣，需要费用为 6 / 2 = 3 。
从 1 前往 2 并使用一次折扣，需要费用为 7 / 2 = 3 。
从 2 前往 3 并使用一次折扣，需要费用为 5 / 2 = 2 。
从 0 前往 3 最小费用为 3 + 3 + 2 = 8 。

示例 3：

输入：n = 4, highways = [[0,1,3],[2,3,2]], discounts = 0
输出：-1
解释：
不存在从 0 前往 3 的路径，所以返回 -1 。

 

提示:

• 2 <= n <= 1000
• 1 <= highways.length <= 1000
• highways[i].length == 3
• 0 <= city1i, city2i <= n - 1
• city1i != city2i
• 0 <= tolli <= 105
• 0 <= discounts <= 500
• 任意两个城市之间最多只有一条公路相连

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

基于 Doocs 分层图 Dijkstra 参考改写。状态 (城市, 已用折扣数)，每条道路可按原价前往同层，或按 toll/2 向下一层。堆中先弹出的终点状态就是全局最小费用，过期状态跳过。n 为城市数、m 为道路数、d 为折扣数，时间 O((n+m)(d+1) log(n(d+1)))，空间 O(m+n(d+1))。入口 minimumCost；折扣整除向下，边权非负。

出处：Doocs 原题与题解，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；题意、参考及本 Go 改写采用 CC BY-SA 4.0。

// 题意与参考：Doocs LeetCode，CC BY-SA 4.0。
// https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/2000-2099/2093.Minimum%20Cost%20to%20Reach%20City%20With%20Discounts/README.md
// Go 实现与测试沿用 CC BY-SA 4.0；来源性质见配套说明。
import "container/heap"

type state struct{ city, used, cost int }
type minHeap []state

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].cost < h[j].cost }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)        { *h = append(*h, x.(state)) }
func (h *minHeap) Pop() any          { a := *h; x := a[len(a)-1]; *h = a[:len(a)-1]; return x }
func minimumCost(n int, highways [][]int, discounts int) int {
	type edge struct{ to, cost int }
	graph := make([][]edge, n)
	for _, e := range highways {
		graph[e[0]] = append(graph[e[0]], edge{e[1], e[2]})
		graph[e[1]] = append(graph[e[1]], edge{e[0], e[2]})
	}
	dist := make([][]int, n)
	for i := range dist {
		dist[i] = make([]int, discounts+1)
		for j := range dist[i] {
			dist[i][j] = int(^uint(0) >> 1)
		}
	}
	dist[0][0] = 0
	h := &minHeap{{}}
	for h.Len() > 0 {
		s := heap.Pop(h).(state)
		if s.cost != dist[s.city][s.used] {
			continue
		}
		if s.city == n-1 {
			return s.cost
		}
		for _, e := range graph[s.city] {
			for use := 0; use <= 1 && s.used+use <= discounts; use++ {
				price := e.cost
				if use == 1 {
					price /= 2
				}
				d := s.cost + price
				u := s.used + use
				if d < dist[e.to][u] {
					dist[e.to][u] = d
					heap.Push(h, state{e.to, u, d})
				}
			}
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

2097. 合法重新排列数对

困难1 种解法

标签：深度优先搜索、图、数组、欧拉路径、欧拉回路、半欧拉图

题目、示例与约束

给你一个下标从 0 开始的二维整数数组 pairs ，其中 pairs[i] = [starti, endi] 。如果 pairs 的一个重新排列，满足对每一个下标 i （ 1 <= i < pairs.length ）都有 endi-1 == starti ，那么我们就认为这个重新排列是 pairs 的一个 合法重新排列 。

请你返回 任意一个 pairs 的合法重新排列。

注意：数据保证至少存在一个 pairs 的合法重新排列。

 

示例 1：

输入：pairs = [[5,1],[4,5],[11,9],[9,4]]
输出：[[11,9],[9,4],[4,5],[5,1]]
解释：
输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti 。
end0 = 9 == 9 = start1 
end1 = 4 == 4 = start2
end2 = 5 == 5 = start3

示例 2：

输入：pairs = [[1,3],[3,2],[2,1]]
输出：[[1,3],[3,2],[2,1]]
解释：
输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti 。
end0 = 3 == 3 = start1
end1 = 2 == 2 = start2
重新排列后的数组 [[2,1],[1,3],[3,2]] 和 [[3,2],[2,1],[1,3]] 都是合法的。

示例 3：

输入：pairs = [[1,2],[1,3],[2,1]]
输出：[[1,2],[2,1],[1,3]]
解释：
输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti 。
end0 = 2 == 2 = start1
end1 = 1 == 1 = start2

 

提示：

• 1 <= pairs.length <= 105
• pairs[i].length == 2
• 0 <= starti, endi <= 109
• starti != endi
• pairs 中不存在一模一样的数对。
• 至少 存在 一个合法的 pairs 重新排列。

方法一：Go 实现（灵茶山艾府） · Go 实现

灵茶山艾府 · 源码 · MIT 许可

本站根据 Go 源码整理，非作者原文。

思路：把每个数对看成一条有向边。若存在出度比入度大一的点，就从它开始，否则任选有出边的点。按 Hierholzer 方法递归消费出边，回溯时记录当前边，最后反转记录顺序，得到每条边恰好使用一次的欧拉路径。题目保证存在合法排列。

复杂度：设数对数即边数为 m，不同端点数为 v。按哈希映射平均常数时间计算，建图和遍历时间为 O(v+m)，辅助空间为 O(v+m)，包含邻接表、结果及最坏 O(m) 的递归栈；因 v≤2m，也可统一写为 O(m)。

/* 有向图欧拉路径

本题与 [332. 重新安排行程](https://leetcode-cn.com/problems/reconstruct-itinerary/) 一样，都可以抽象成如下问题：

> 给你一张有向图，在这张有向图中找到一条欧拉路径。

对于此题，由于题目保证有解，所以有向图肯定是欧拉图或半欧拉图。

我们需要找到一个起点，如果是欧拉图，那么随便找一个点都行，如果是半欧拉图，那么找到一个出度比入度大 1 的点，把它当成起点，然后按照 332 给出的算法来求解。

*/

// github.com/EndlessCheng/codeforces-go
func validArrangement(pairs [][]int) [][]int {
	type edge struct{ to, idx int }
	g := map[int][]edge{}
	inDeg := map[int]int{}
	for i, p := range pairs {
		v, w := p[0], p[1]
		g[v] = append(g[v], edge{w, i}) // 建图（有向图）
		inDeg[w]++ // 统计入度
	}

	start := 0
	for i, es := range g {
		if len(es) == inDeg[i]+1 { // 如果存在出度比入度大 1 的点，那就把它当成起点
			start = i
			break
		}
		start = i // 或者随便找一个点当起点
	}

	m := len(pairs)
	ans := make([][]int, 0, m)
	var dfs func(int)
	dfs = func(v int) {
		for len(g[v]) > 0 {
			e := g[v][0]
			g[v] = g[v][1:]
			dfs(e.to)
			ans = append(ans, pairs[e.idx]) // 保存所有边
		}
	}
	dfs(start)
	for i := 0; i < m/2; i++ {
		ans[i], ans[m-1-i] = ans[m-1-i], ans[i]
	}
	return ans
}

力扣原题 · Doocs 题解来源

2101. 引爆最多的炸弹

中等1 种解法

标签：深度优先搜索、广度优先搜索、图、几何、数组、数学

题目、示例与约束

给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。

炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围的 半径 。

你需要选择引爆 一个 炸弹。当这个炸弹被引爆时，所有 在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。

给你数组 bombs ，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。

 

示例 1：

输入：bombs = [[2,1,3],[6,1,4]]
输出：2
解释：
上图展示了 2 个炸弹的位置和爆炸范围。
如果我们引爆左边的炸弹，右边的炸弹不会被影响。
但如果我们引爆右边的炸弹，两个炸弹都会爆炸。
所以最多能引爆的炸弹数目是 max(1, 2) = 2 。

示例 2：

输入：bombs = [[1,1,5],[10,10,5]]
输出：1
解释：
引爆任意一个炸弹都不会引爆另一个炸弹。所以最多能引爆的炸弹数目为 1 。

示例 3：

输入：bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
输出：5
解释：
最佳引爆炸弹为炸弹 0 ，因为：
- 炸弹 0 引爆炸弹 1 和 2 。红色圆表示炸弹 0 的爆炸范围。
- 炸弹 2 引爆炸弹 3 。蓝色圆表示炸弹 2 的爆炸范围。
- 炸弹 3 引爆炸弹 4 。绿色圆表示炸弹 3 的爆炸范围。
所以总共有 5 个炸弹被引爆。

 

提示：

• 1 <= bombs.length <= 100
• bombs[i].length == 3
• 1 <= xi, yi, ri <= 105

方法一：BFS · Go 实现

思考

一次引爆会沿「落在爆炸半径内」的关系连锁下去，需要求从某一枚炸弹出发可达的炸弹数最大值。若把每对炸弹都当作无向关系处理，则会漏掉半径不同所造成的单向可达；若每次引爆都重新扫描全部炸弹，重复计算过多。

$n\le 100$，预先对每对炸弹用距离与半径建有向图 $g$ 只需 $O(n^2)$。从图上任意一点出发的连锁引爆即为有向图上的可达点集，用 BFS 即可在 $O(n^2)$ 内求出。

为此先枚举有序对建边，再以每一枚炸弹为起点做 BFS；一旦某次搜索覆盖全部 $n$ 枚即可提前返回。

我们定义一个长度为 $n$ 的数组 $g$，其中 $g[i]$ 表示炸弹 $i$ 的爆炸范围内可以引爆的所有炸弹的下标。

然后，我们遍历所有炸弹，对于两个炸弹 $(x_1,y_1,r_1)$ 和 $(x_2,y_2,r_2)$，我们计算它们之间的距离 $\mathit{\text{dist}}=\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$。如果 $\mathit{\text{dist}}\le r_1$，那么炸弹 $i$ 的爆炸范围内可以引爆炸弹 $j$，我们就将 $j$ 添加到 $g[i]$ 中。如果 $\mathit{\text{dist}}\le r_2$，那么炸弹 $j$ 的爆炸范围内可以引爆炸弹 $i$，我们就将 $i$ 添加到 $g[j]$ 中。

接下来，我们遍历所有炸弹，对于每个炸弹 $k$，我们使用广度优先搜索计算炸弹 $k$ 的爆炸范围内可以引爆的所有炸弹的下标，并记录下来。如果这些炸弹的数量等于 $n$，那么我们就可以引爆所有炸弹，直接返回 $n$。否则，我们记录下来这些炸弹的数量，并返回最大值。

时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 为炸弹的数量。

func maximumDetonation(bombs [][]int) (ans int) {
	n := len(bombs)
	g := make([][]int, n)
	for i, p1 := range bombs[:n-1] {
		for j := i + 1; j < n; j++ {
			p2 := bombs[j]
			dist := math.Hypot(float64(p1[0]-p2[0]), float64(p1[1]-p2[1]))
			if dist <= float64(p1[2]) {
				g[i] = append(g[i], j)
			}
			if dist <= float64(p2[2]) {
				g[j] = append(g[j], i)
			}
		}
	}
	for k := 0; k < n; k++ {
		q := []int{k}
		vis := make([]bool, n)
		vis[k] = true
		cnt := 0
		for len(q) > 0 {
			i := q[0]
			q = q[1:]
			cnt++
			for _, j := range g[i] {
				if !vis[j] {
					vis[j] = true
					q = append(q, j)
				}
			}
		}
		if cnt == n {
			return n
		}
		ans = max(ans, cnt)
	}
	return
}

力扣原题 · Doocs 题解来源

2115. 从给定原材料中找到所有可以做出的菜

中等1 种解法

标签：图、拓扑排序、数组、哈希表、字符串、有向无环图

题目、示例与约束

你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] ，如果你有它 所有 的原材料 ingredients[i] ，那么你可以 做出 这道菜。一份食谱也可以是 其它 食谱的原料，也就是说 ingredients[i] 可能包含 recipes 中另一个字符串。

同时给你一个字符串数组 supplies ，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。

请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。

注意两道菜在它们的原材料中可能互相包含。

 

示例 1：

输入：recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
输出：["bread"]
解释：
我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。

示例 2：

输入：recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
输出：["bread","sandwich"]
解释：
我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。
我们可以做出 "sandwich" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 。

示例 3：

输入：recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]
输出：["bread","sandwich","burger"]
解释：
我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。
我们可以做出 "sandwich" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 。
我们可以做出 "burger" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 和 "sandwich" 。

示例 4：

输入：recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast"]
输出：[]
解释：
我们没法做出任何菜，因为我们只有原材料 "yeast" 。

 

提示：

• n == recipes.length == ingredients.length
• 1 <= n <= 100
• 1 <= ingredients[i].length, supplies.length <= 100
• 1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10
• recipes[i], ingredients[i][j] 和 supplies[k] 只包含小写英文字母。
• 所有 recipes 和 supplies 中的值互不相同。
• ingredients[i] 中的字符串互不相同。

方法一：拓扑排序 · Go 实现

思考

一道菜能否做成取决于其原料是否都能从初始供应或已做成的菜中获得，依赖关系构成有向图。若对每道菜反复检查原料，可能因相互等待而重复扫描，也难以处理链式解锁。

将原料指向依赖它的菜，入度为该菜所需原料种数。初始供应相当于入度为零的起点，拓扑序中入度降为零的菜即可做成，并可作为新的供应继续解锁。

为此建图后把 $\mathit{\text{supplies}}$ 当作队列做拓扑排序，入度归零的菜加入答案。

首先，我们可以将每道菜看成一个节点，每个节点的入度表示其所需的原材料数量。我们可以通过拓扑排序的方式，找到所有可以做出的菜。

func findAllRecipes(recipes []string, ingredients [][]string, supplies []string) []string {
	g := map[string][]string{}
	indeg := map[string]int{}
	for i, a := range recipes {
		for _, b := range ingredients[i] {
			g[b] = append(g[b], a)
		}
		indeg[a] = len(ingredients[i])
	}
	q := []string{}
	for _, s := range supplies {
		q = append(q, s)
	}
	ans := []string{}
	for len(q) > 0 {
		for n := len(q); n > 0; n-- {
			i := q[0]
			q = q[1:]
			for _, j := range g[i] {
				indeg[j]--
				if indeg[j] == 0 {
					ans = append(ans, j)
					q = append(q, j)
				}
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2123. 使矩阵中的 1 互不相邻的最小操作数 🔒

困难1 种解法

标签：深度优先搜索、图、数组、矩阵、Edmonds–Karp 算法、Dinic 算法、MPM 算法、Push-Relabel 算法、网络流

题目、示例与约束

给你一个 下标从 0 开始 的矩阵 grid。每次操作，你可以把 grid 中的 一个 1 变成 0 。

如果一个矩阵中，没有 1 与其它的 1 四连通（也就是说所有 1 在上下左右四个方向上不能与其他 1 相邻），那么该矩阵就是 完全独立 的。

请返回让 grid 成为 完全独立 的矩阵的 最小操作数。

 

示例 1:

输入: grid = [[1,1,0],[0,1,1],[1,1,1]]
输出: 3
解释: 可以进行三次操作（把 grid[0][1], grid[1][2] 和 grid[2][1] 变成 0）。
操作后的矩阵中的所有的 1 与其它 1 均不相邻，因此矩阵是完全独立的。

示例 2:

输入: grid = [[0,0,0],[0,0,0],[0,0,0]]
输出: 0
解释: 矩阵中没有 1，此时矩阵也是完全独立的，因此无需操作，返回 0。

示例 3:

输入: grid = [[0,1],[1,0]]
输出: 0
解释: 矩阵中的所有的 1 与其它 1 均不相邻，已经是完全独立的，因此无需操作，返回 0。

 

提示:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 是 0 或者 1.

方法一：匈牙利算法 · Go 实现

思考

每次操作去掉一个 $1$，目标是消灭所有相邻的 $1$ 对，即覆盖全部「相邻 $1$」边的最小点数。网格是二分图：按 $i+j$ 的奇偶分部，相邻格必分属两侧。

二分图最小点覆盖等于最大匹配。 $1$ 的个数与边数在网格规模下可用匈牙利算法求匹配。

将奇数格上的 $1$ 连向相邻的 $1$，对每个左侧点寻找增广路，匹配数即为最少操作次数。

我们注意到，如果矩阵中的两个 $1$ 相邻，那么它们一定属于不同的组。因此，我们可以把矩阵中所有的 $1$ 视为点，相邻的两个 $1$ 之间连一条边，构建二分图。

那么，问题可以转化为求二分图最小点覆盖，也即选出最少数目的点来覆盖所有的边。由于二分图的最小点覆盖数等于最大匹配数，因此我们可以使用匈牙利算法求出二分图的最大匹配数。

匈牙利算法的核心思想是，不断地从未匹配的点出发，寻找增广路径，直到没有增广路径为止，就得到了最大匹配。

时间复杂度 $O(m\times n)$，其中 $n$ 和 $m$ 分别是矩阵中 $1$ 的数目以及边的数目。

func minimumOperations(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	vis := map[int]bool{}
	match := make([]int, m*n)
	for i := range match {
		match[i] = -1
	}
	g := map[int][]int{}
	for i, row := range grid {
		for j, v := range row {
			if (i+j)&1 == 1 && v == 1 {
				x := i*n + j
				if i < m-1 && grid[i+1][j] == 1 {
					g[x] = append(g[x], x+n)
				}
				if i > 0 && grid[i-1][j] == 1 {
					g[x] = append(g[x], x-n)
				}
				if j < n-1 && grid[i][j+1] == 1 {
					g[x] = append(g[x], x+1)
				}
				if j > 0 && grid[i][j-1] == 1 {
					g[x] = append(g[x], x-1)
				}
			}
		}
	}
	var find func(int) int
	find = func(i int) int {
		for _, j := range g[i] {
			if !vis[j] {
				vis[j] = true
				if match[j] == -1 || find(match[j]) == 1 {
					match[j] = i
					return 1
				}
			}
		}
		return 0
	}
	for i := range g {
		ans += find(i)
		vis = map[int]bool{}
	}
	return
}

力扣原题 · Doocs 题解来源

2127. 参加会议的最多员工数

困难1 种解法

标签：深度优先搜索、图、拓扑排序、数组、动态规划、Kosaraju 算法、Tarjan 强连通分量算法

题目、示例与约束

一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。

员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。

给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。

 

示例 1：

输入：favorite = [2,2,1,2]
输出：3
解释：
上图展示了公司邀请员工 0，1 和 2 参加会议以及他们在圆桌上的座位。
没办法邀请所有员工参与会议，因为员工 2 没办法同时坐在 0，1 和 3 员工的旁边。
注意，公司也可以邀请员工 1，2 和 3 参加会议。
所以最多参加会议的员工数目为 3 。

示例 2：

输入：favorite = [1,2,0]
输出：3
解释：
每个员工都至少是另一个员工喜欢的员工。所以公司邀请他们所有人参加会议的前提是所有人都参加了会议。
座位安排同图 1 所示：
- 员工 0 坐在员工 2 和 1 之间。
- 员工 1 坐在员工 0 和 2 之间。
- 员工 2 坐在员工 1 和 0 之间。
参与会议的最多员工数目为 3 。

示例 3：

输入：favorite = [3,0,1,4,1]
输出：4
解释：
上图展示了公司可以邀请员工 0，1，3 和 4 参加会议以及他们在圆桌上的座位。
员工 2 无法参加，因为他喜欢的员工 1 旁边的座位已经被占领了。
所以公司只能不邀请员工 2 。
参加会议的最多员工数目为 4 。

 

提示：

• n == favorite.length
• 2 <= n <= 105
• 0 <= favorite[i] <= n - 1
• favorite[i] != i

方法一：图的最大环 + 最长链 · Go 实现

思考

每人恰好喜欢一人，图由若干基环内向树组成。圆桌要求相邻都互相喜欢，因而要么坐在同一个环上，要么利用长度为 $2$ 的互喜欢对把两侧的链拼在一起。不同环互不连通，不能混坐。

环长至少为 $3$ 时，只能取该环本身，答案候选为全局最长环。所有长度为 $2$ 的环彼此可以同时入席，各自再接上指向该点的最长入链，这些链的长度可在拓扑消点后得到。

为此分别求最大环长，以及所有二元环上 $\mathit{\text{dist}}$ 之和，取较大者。

我们观察发现，题目中员工的喜好关系可以看作一个有向图，这个有向图可以分成多个“基环内向树”的结构。在每个结构中，包含一个环，而环上的每个节点都连接着一棵树。

什么是“基环内向树”？首先，基环树是一个具有 $n$ 个节点 $n$ 条边的有向图，而内向树是指这个有向图中，每个节点都有且仅有一条出边。本题中，每个员工都有且仅有一个喜欢的员工，因此，构成的有向图可以由多个“基环内向树”构成。

<img alt="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2100-2199/2127.Maximum Employees to Be Invited to a Meeting/images/05Dxh9.png"></p>

对于本题，我们可以求出图的最大环的长度，这里我们只需要求出最大的一个环的长度，这是因为，如果有多个环，那么不同环之间是不连通的，不符合题意。

另外，对于环的大小等于 $2$ 的长度，即存在两个员工互相喜欢，那么我们可以把这两个员工安排在一起，如果这两个员工各自被别的员工喜欢，那么我们只需要把喜欢他们的员工安排在他们的旁边即可。如果有多个这样的情况，我们可以把他们都安排上。

因此，问题实际上等价于求出图的最大环的长度，以及所有长度为 $2$ 的环加上其最长链。求这两者的最大值即可。求最长链到长度为 $2$ 的环，我们可以使用拓扑排序。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 favorite 的长度。

相似题目：

• 2360. 图中的最长环

func maximumInvitations(favorite []int) int {
	a, b := maxCycle(favorite), topologicalSort(favorite)
	return max(a, b)
}

func maxCycle(fa []int) int {
	n := len(fa)
	vis := make([]bool, n)
	ans := 0
	for i := range fa {
		if vis[i] {
			continue
		}
		j := i
		cycle := []int{}
		for !vis[j] {
			cycle = append(cycle, j)
			vis[j] = true
			j = fa[j]
		}
		for k, v := range cycle {
			if v == j {
				ans = max(ans, len(cycle)-k)
				break
			}
		}
	}
	return ans
}

func topologicalSort(fa []int) int {
	n := len(fa)
	indeg := make([]int, n)
	dist := make([]int, n)
	for i := range fa {
		dist[i] = 1
	}
	for _, v := range fa {
		indeg[v]++
	}
	q := []int{}
	for i, v := range indeg {
		if v == 0 {
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		i := q[0]
		q = q[1:]
		dist[fa[i]] = max(dist[fa[i]], dist[i]+1)
		indeg[fa[i]]--
		if indeg[fa[i]] == 0 {
			q = append(q, fa[i])
		}
	}
	ans := 0
	for i := range fa {
		if i == fa[fa[i]] {
			ans += dist[i]
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2192. 有向无环图中一个节点的所有祖先

中等1 种解法

标签：深度优先搜索、广度优先搜索、图、拓扑排序、有向无环图

题目、示例与约束

给你一个正整数 n ，它表示一个 有向无环图 中节点的数目，节点编号为 0 到 n - 1 （包括两者）。

给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。

请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有 祖先 ，这些祖先节点 升序 排序。

如果 u 通过一系列边，能够到达 v ，那么我们称节点 u 是节点 v 的 祖先 节点。

 

示例 1：

输入：n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
输出：[[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
解释：
上图为输入所对应的图。
- 节点 0 ，1 和 2 没有任何祖先。
- 节点 3 有 2 个祖先 0 和 1 。
- 节点 4 有 2 个祖先 0 和 2 。
- 节点 5 有 3 个祖先 0 ，1 和 3 。
- 节点 6 有 5 个祖先 0 ，1 ，2 ，3 和 4 。
- 节点 7 有 4 个祖先 0 ，1 ，2 和 3 。

示例 2：

输入：n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
输出：[[],[0],[0,1],[0,1,2],[0,1,2,3]]
解释：
上图为输入所对应的图。
- 节点 0 没有任何祖先。
- 节点 1 有 1 个祖先 0 。
- 节点 2 有 2 个祖先 0 和 1 。
- 节点 3 有 3 个祖先 0 ，1 和 2 。
- 节点 4 有 4 个祖先 0 ，1 ，2 和 3 。

 

提示：

• 1 <= n <= 1000
• 0 <= edges.length <= min(2000, n * (n - 1) / 2)
• edges[i].length == 2
• 0 <= fromi, toi <= n - 1
• fromi != toi
• 图中不会有重边。
• 图是 有向 且 无环 的。

方法一：BFS · Go 实现

思考

DAG 中求每个点的全部祖先，并按编号升序。若对每个点反向 DFS，重复走入边较多时偏慢，且还要去重排序。 $n\le 1000$，从每个点正向遍历子孙，把该点写入子孙的祖先列表， naturally 按起点编号有序。

先建邻接表，再对每个 $i$ 做 BFS，把 $i$ 追加到所有可达点。访问集合避免重复入队。

答案数组的每一行在插入时已按 $i$ 递增。

我们先根据二维数组 $edges$ 构建邻接表 $g$，其中 $g[i]$ 表示节点 $i$ 的所有后继节点。

然后我们从小到大枚举节点 $i$ 作为祖先节点，使用 BFS 搜索节点 $i$ 的所有后继节点，把节点 $i$ 加入这些后继节点的祖先列表中。

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

func getAncestors(n int, edges [][]int) [][]int {
	g := make([][]int, n)
	for _, e := range edges {
		g[e[0]] = append(g[e[0]], e[1])
	}
	ans := make([][]int, n)
	bfs := func(s int) {
		q := []int{s}
		vis := make([]bool, n)
		vis[s] = true
		for len(q) > 0 {
			i := q[0]
			q = q[1:]
			for _, j := range g[i] {
				if !vis[j] {
					vis[j] = true
					q = append(q, j)
					ans[j] = append(ans[j], s)
				}
			}
		}
	}
	for i := 0; i < n; i++ {
		bfs(i)
	}
	return ans
}

力扣原题 · Doocs 题解来源

2203. 包含要求路径的最小带权子图

困难1 种解法

标签：图、最短路、堆（优先队列）

题目、示例与约束

给你一个整数 n ，它表示一个 带权有向 图的节点数，节点编号为 0 到 n - 1 。

同时给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi, weighti] ，表示从 fromi 到 toi 有一条边权为 weighti 的 有向 边。

最后，给你三个 互不相同 的整数 src1 ，src2 和 dest ，表示图中三个不同的点。

请你从图中选出一个 边权和最小 的子图，使得从 src1 和 src2 出发，在这个子图中，都 可以 到达 dest 。如果这样的子图不存在，请返回 -1 。

子图 中的点和边都应该属于原图的一部分。子图的边权和定义为它所包含的所有边的权值之和。

 

示例 1：

输入：n = 6, edges = [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], src1 = 0, src2 = 1, dest = 5
输出：9
解释：
上图为输入的图。
蓝色边为最优子图之一。
注意，子图 [[1,0,3],[0,5,6]] 也能得到最优解，但无法在满足所有限制的前提下，得到更优解。

示例 2：

输入：n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
输出：-1
解释：
上图为输入的图。
可以看到，不存在从节点 1 到节点 2 的路径，所以不存在任何子图满足所有限制。

 

提示：

• 3 <= n <= 105
• 0 <= edges.length <= 105
• edges[i].length == 3
• 0 <= fromi, toi, src1, src2, dest <= n - 1
• fromi != toi
• src1 ，src2 和 dest 两两不同。
• 1 <= weight[i] <= 105

方法一：Go 实现（灵茶山艾府） · Go 实现

灵茶山艾府 · 源码 · MIT 许可

本站根据 Go 源码整理，非作者原文。

思路：分别在原图上从 src1、src2 跑 Dijkstra，得到到各点的最短距离；再在反图上从 dest 跑一次，得到原图中各点到 dest 的距离。枚举两条路径开始共享后续路线的汇合点 x，取三段距离 d1[x]+d2[x]+d3[x] 的最小值。若所有汇合点都不可达，就返回 -1。堆采用懒更新，弹出过时距离时直接跳过。

复杂度：设节点数为 n、边数为 m。懒更新堆最多保存 O(m) 个条目，三次最短路的总时间上界为 O(n+m log(m+2))，辅助空间为 O(n+m)，包含正反邻接表、距离数组和堆。

import (
	"container/heap"
	"math"
)

// github.com/EndlessCheng/codeforces-go
const inf = math.MaxInt / 3 // 防止计算 d1[x] + d2[x] + d3[x] 时溢出

type edge struct{ to, wt int }

func minimumWeight(n int, edges [][]int, src1, src2, dest int) int64 {
	g := make([][]edge, n)
	rg := make([][]edge, n) // 反图，用于计算从 dest 出发的最短路
	for _, e := range edges {
		x, y, wt := e[0], e[1], e[2]
		g[x] = append(g[x], edge{y, wt})
		rg[y] = append(rg[y], edge{x, wt})
	}

	d1 := dijkstra(g, src1)
	d2 := dijkstra(g, src2)
	d3 := dijkstra(rg, dest)

	ans := inf
	for x := range n { // 枚举相遇点 x
		ans = min(ans, d1[x]+d2[x]+d3[x])
	}

	if ans == inf {
		return -1
	}
	return int64(ans)
}

func dijkstra(g [][]edge, start int) []int {
	dis := make([]int, len(g))
	for i := range dis {
		dis[i] = inf
	}
	dis[start] = 0 // 起点到自己的距离是 0
	// 堆中保存 (起点到节点 x 的最短路长度，节点 x)
	h := &hp{{0, start}}

	for h.Len() > 0 {
		p := heap.Pop(h).(pair)
		disX, x := p.dis, p.x
		if disX > dis[x] { // x 之前出堆过
			continue
		}
		for _, e := range g[x] {
			y := e.to
			newDisY := disX + e.wt
			if newDisY < dis[y] {
				dis[y] = newDisY // 更新 x 的邻居的最短路
				// 懒更新堆：只插入数据，不更新堆中数据
				// 相同节点可能有多个不同的 newDisY，除了最小的 newDisY，其余值都会触发上面的 continue
				heap.Push(h, pair{newDisY, y})
			}
		}
	}

	return dis
}

type pair struct{ dis, x int }
type hp []pair

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
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.(pair)) }
func (h *hp) Pop() (v any)      { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }

力扣原题 · Doocs 题解来源

2204. 无向图中到环的距离 🔒

困难1 种解法

标签：深度优先搜索、广度优先搜索、图、拓扑排序

题目、示例与约束

给定一个正整数 n，表示一个 连通无向图 中的节点数，该图 只包含一个 环。节点编号为 0 ~ n - 1(含)。

你还得到了一个二维整数数组 edges，其中 edges[i] = [node1i, node2i] 表示有一条 双向 边连接图中的 node1i 和 node2i。

两个节点 a 和 b 之间的距离定义为从 a 到 b 所需的 最小边数。

返回一个长度为 n 的整数数组 answer，其中 answer[i] 是第 i 个节点与环中任何节点之间的最小距离。

示例 1:

输入: n = 7, edges = [[1,2],[2,4],[4,3],[3,1],[0,1],[5,2],[6,5]]
输出: [1,0,0,0,0,1,2]
解释:
节点 1, 2, 3, 和 4 来自环。
0 到 1 的距离是 1。
1 到 1 的距离是 0。
2 到 2 的距离是 0。
3 到 3 的距离是 0。
4 到 4 的距离是 0。
5 到 2 的距离是 1。
6 到 2 的距离是 2。

示例 2:

输入: n = 9, edges = [[0,1],[1,2],[0,2],[2,6],[6,7],[6,8],[0,3],[3,4],[3,5]]
输出: [0,0,0,1,2,2,1,2,2]
解释:
节点 0, 1, 和 2 来自环.
0 到 0 的距离是 0。
1 到 1 的距离是 0。
2 到 2 的距离是 0。
3 到 0 的距离是 1。
4 到 0 的距离是 2。
5 到 0 的距离是 2。
6 到 2 的距离是 1。
7 到 2 的距离是 2。
8 到 2 的距离是 2。

 

提示:

• 3 <= n <= 105
• edges.length == n
• edges[i].length == 2
• 0 <= node1i, node2i <= n - 1
• node1i != node2i
• 图是连通的。
• 这个图只有一个环。
• 任何顶点对之间最多只有一条边。

方法一：拓扑排序 · Go 实现

思考

图由一个环加上若干棵挂在环上的树构成。若从每个点 BFS 找环，时间可达 $O(n^2)$，在 $n$ 与边数同阶时偏贵。环上的点距离为 $0$，树上的点距离等于沿唯一路径走到环的边数。

注意到度为 $1$ 的点一定不在环上，可以像剥洋葱一样反复删除。用队列收集当前度为 $1$ 的点，删除时记录父节点 $f[i]$，并把邻居度数减一。删完后剩下的连通分量即是环。

再按删除的逆序回填：环上距离已是 $0$，被删点 $i$ 的距离为 $ans[f[i]]+1$。一遍拓扑即可得到所有点到环的距离。

我们可以先将 $edges$ 中的边转换成邻接表 $g$，其中 $g[i]$ 表示节点 $i$ 的所有邻接节点，用集合表示。

接下来，我们由外向内，逐层删除节点，直到最终只剩下一个环。具体做法如下：

我们先找出所有度为 $1$ 的节点，将这些节点从图中删除，如果删除后，其邻接节点的度变为 $1$，则将其加入队列 $q$ 中。过程中，我们按顺序记录下所有被删除的节点，记为 $seq$；并且，我们用一个数组 $f$ 记录每个节点相邻的且更接近环的节点，即 $f[i]$ 表示节点 $i$ 的相邻且更接近环的节点。

最后，我们初始化一个长度为 $n$ 的答案数组 $ans$，其中 $ans[i]$ 表示节点 $i$ 到环中任意节点的最小距离，初始时 $ans[i]=0$。然后，我们从 $seq$ 的末尾开始遍历，对于每个节点 $i$，我们可以由它的相邻节点 $f[i]$ 得到 $ans[i]$ 的值，即 $ans[i]=ans[f[i]]+1$。

遍历结束后，返回答案数组 $ans$ 即可。

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

相似题目：

• 2603. 收集树中金币

func distanceToCycle(n int, edges [][]int) []int {
	g := make([]map[int]bool, n)
	for i := range g {
		g[i] = map[int]bool{}
	}
	for _, e := range edges {
		a, b := e[0], e[1]
		g[a][b] = true
		g[b][a] = true
	}
	q := []int{}
	for i := 0; i < n; i++ {
		if len(g[i]) == 1 {
			q = append(q, i)
		}
	}
	f := make([]int, n)
	seq := []int{}
	for len(q) > 0 {
		i := q[0]
		q = q[1:]
		seq = append(seq, i)
		for j := range g[i] {
			delete(g[j], i)
			f[i] = j
			if len(g[j]) == 1 {
				q = append(q, j)
			}
		}
		g[i] = map[int]bool{}
	}
	ans := make([]int, n)
	for k := len(seq) - 1; k >= 0; k-- {
		i := seq[k]
		ans[i] = ans[f[i]] + 1
	}
	return ans
}

力扣原题 · Doocs 题解来源

2242. 节点序列的最大得分

困难1 种解法

标签：图、数组、枚举、排序

题目、示例与约束

给你一个 n 个节点的 无向图 ，节点编号为 0 到 n - 1 。

给你一个下标从 0 开始的整数数组 scores ，其中 scores[i] 是第 i 个节点的分数。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] ，表示节点 ai 和 bi 之间有一条 无向 边。

一个合法的节点序列如果满足以下条件，我们称它是 合法的 ：

• 序列中每 相邻 节点之间有边相连。
• 序列中没有节点出现超过一次。

节点序列的分数定义为序列中节点分数之 和 。

请你返回一个长度为 4 的合法节点序列的最大分数。如果不存在这样的序列，请你返回 -1 。

 

示例 1：

输入：scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
输出：24
解释：上图为输入的图，节点序列为 [0,1,2,3] 。
节点序列的分数为 5 + 2 + 9 + 8 = 24 。
观察可知，没有其他节点序列得分和超过 24 。
注意节点序列 [3,1,2,0] 和 [1,0,2,3] 也是合法的，且分数为 24 。
序列 [0,3,2,4] 不是合法的，因为没有边连接节点 0 和 3 。

示例 2：

输入：scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]]
输出：-1
解释：上图为输入的图。
没有长度为 4 的合法序列，所以我们返回 -1 。

 

提示：

• n == scores.length
• 4 <= n <= 5 * 104
• 1 <= scores[i] <= 108
• 0 <= edges.length <= 5 * 104
• edges[i].length == 2
• 0 <= ai, bi <= n - 1
• ai != bi
• 不会有重边。

方法一：Go 实现（灵茶山艾府） · Go 实现

灵茶山艾府 · 源码 · MIT 许可 · 原题解

提示 1

设序列为 $a-x-y-b$（$-$ 表示边），枚举 $\mathit{\text{edges}}$ 中的每条边，作为序列中的 $x-y$。

提示 2

根据提示 1，我们需要把与 $x$ 相邻的点中，分数最大且不同于 $y$ 和 $b$ 的点作为 $a$；把与 $y$ 相邻的点中，分数最大且不同于 $x$ 和 $a$ 的点作为 $b$。

提示 3

与 $x$ 相邻的点中，由于只需要与 $y$ 和 $b$ 不一样，我们仅需要保留分数最大的三个点，$a$ 必定在这三个点中。

提示 4

剩下要做的，就是在枚举 $\mathit{\text{edges}}$ 前，预处理出这三个点。

代码实现时，可以用排序、堆或者分治（nth_element）求前三大。

import "sort"

// github.com/EndlessCheng/codeforces-go
func maximumScore(scores []int, edges [][]int) int {
	type nb struct{ to, s int }
	g := make([][]nb, len(scores))
	for _, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], nb{y, scores[y]})
		g[y] = append(g[y], nb{x, scores[x]})
	}
	for i, vs := range g {
		sort.Slice(vs, func(i, j int) bool { return vs[i].s > vs[j].s })
		if len(vs) > 3 {
			vs = vs[:3]
		}
		g[i] = vs
	}

	ans := -1
	for _, e := range edges {
		x, y := e[0], e[1]
		for _, p := range g[x] {
			for _, q := range g[y] {
				if p.to != y && q.to != x && p.to != q.to {
					ans = max(ans, p.s+scores[x]+scores[y]+q.s)
				}
			}
		}
	}
	return ans
}

func max(a, b int) int { if b > a { return b }; return a }

力扣原题 · Doocs 题解来源

2246. 相邻字符不同的最长路径

困难2 种解法

标签：树、深度优先搜索、图、拓扑排序、数组、字符串

题目、示例与约束

给你一棵 树（即一个连通、无向、无环图），根节点是节点 0 ，这棵树由编号从 0 到 n - 1 的 n 个节点组成。用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树，其中 parent[i] 是节点 i 的父节点，由于节点 0 是根节点，所以 parent[0] == -1 。

另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符。

请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 ，并返回该路径的长度。

 

示例 1：

输入：parent = [-1,0,0,1,1,2], s = "abacbe"
输出：3
解释：任意一对相邻节点字符都不同的最长路径是：0 -> 1 -> 3 。该路径的长度是 3 ，所以返回 3 。
可以证明不存在满足上述条件且比 3 更长的路径。 

示例 2：

输入：parent = [-1,0,0,0], s = "aabc"
输出：3
解释：任意一对相邻节点字符都不同的最长路径是：2 -> 0 -> 3 。该路径的长度为 3 ，所以返回 3 。

 

提示：

• n == parent.length == s.length
• 1 <= n <= 105
• 对所有 i >= 1 ，0 <= parent[i] <= n - 1 均成立
• parent[0] == -1
• parent 表示一棵有效的树
• s 仅由小写英文字母组成

方法一：树形 DP · Go 实现

思考

在树上找一条相邻字符均不同的最长路径。 $n\le {10}^5$，不能枚举端点对。路径要么完全落在某一子树，要么在某点处把两条合法向下链拼起来。

DFS 返回「从当前点向下、且第一步字符不同」的最长链长。对每个儿子先递归；仅当 $s[i]\ne s[j]$ 时，用当前次长链与这条新链更新全局答案，并维护最长向下链。根上再加一（计入自身）。一次遍历即可。

我们先根据数组 $parent$ 构建邻接表 $g$，其中 $g[i]$ 表示节点 $i$ 的所有子节点。

然后我们从根节点开始 DFS，对于每个节点 $i$，我们遍历 $g[i]$ 中的每个子节点 $j$，如果 $s[i]\ne s[j]$，那么我们就可以从 $i$ 节点出发，经过 $j$ 节点，到达某个叶子节点，这条路径的长度为 $x=1+dfs(j)$，我们用 $mx$ 记录最长的一条从节点 $i$ 出发的路径长度。同时，在遍历的过程中，更新答案 $ans=max(ans,mx+x)$。

最后，我们返回 $ans+1$ 即可。

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

func longestPath(parent []int, s string) int {
	n := len(parent)
	g := make([][]int, n)
	for i := 1; i < n; i++ {
		g[parent[i]] = append(g[parent[i]], i)
	}
	ans := 0
	var dfs func(int) int
	dfs = func(i int) int {
		mx := 0
		for _, j := range g[i] {
			x := dfs(j) + 1
			if s[i] != s[j] {
				ans = max(ans, x+mx)
				mx = max(mx, x)
			}
		}
		return mx
	}
	dfs(0)
	return ans + 1
}

方法二：树形 DP + 显式栈 · Go 实现

思考

在树上找一条相邻字符均不同的最长路径。 $n\le {10}^5$，从根递归求每棵子树的向下链，链上的调用深度就是 $n$，会超出递归栈。

这样的路径要么完全落在某一子树，要么在某个点把两条向下链拼起来。离开一个节点时，儿子的向下链已经知道：仅当 $s[i]\ne s[j]$ 时，这条链才能接到 $i$ 上，长度是儿子的链长加 $1$。用当前最长的一条与新链更新全局答案，并留下更长的那条作为本节点的向下链。

显式栈按 $(\mathrm{节}\mathrm{点},\mathrm{状}\mathrm{态})$ 做后序。进入时先压出栈标记再压孩子，离开时按上面的规则更新答案和向下链。最后把答案加 $1$，补上路径经过的节点数。

我们先根据数组 $parent$ 构建邻接表 $g$，其中 $g[i]$ 表示节点 $i$ 的所有子节点。

用显式栈从根做后序。离开节点 $i$ 时，遍历每个子节点 $j$，记 $x$ 为从 $j$ 向下的最长链再加 $1$。若 $s[i]\ne s[j]$，就用已经记下的最长向下链 $mx$ 与 $x$ 更新答案 $ans=max(ans,mx+x)$，再把 $mx$ 更新为 $max(mx,x)$。 $mx$ 是从 $i$ 向下、且第一步字符不同的最长链。

最后，我们返回 $ans+1$ 即可。

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

func longestPath(parent []int, s string) int {
	n := len(parent)
	g := make([][]int, n)
	for i := 1; i < n; i++ {
		g[parent[i]] = append(g[parent[i]], i)
	}
	down := make([]int, n)
	ans := 0
	stk := [][2]int{{0, 0}}
	for len(stk) > 0 {
		cur := stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		i, state := cur[0], cur[1]
		if state == 0 {
			stk = append(stk, [2]int{i, 1})
			for _, j := range g[i] {
				stk = append(stk, [2]int{j, 0})
			}
		} else {
			mx := 0
			for _, j := range g[i] {
				x := down[j] + 1
				if s[i] != s[j] {
					ans = max(ans, x+mx)
					mx = max(mx, x)
				}
			}
			down[i] = mx
		}
	}
	return ans + 1
}

力扣原题 · Doocs 题解来源

2247. K 条高速公路的最大旅行费用 🔒

困难1 种解法

标签：位运算、图、动态规划、位掩码

题目、示例与约束

一系列高速公路连接从 0 到 n - 1 的 n 个城市。给定一个二维整数数组 highways，其中 highways[i] = [city1i, city2i, tolli] 表示有一条高速公路连接 city1i 和city2i，允许一辆汽车从 city1i 前往 city2i，反之亦然，费用为 tolli。

给你一个整数 k，你要正好经过 k 条公路。你可以从任何一个城市出发，但在旅途中每个城市最多只能访问一次。

返回您旅行的最大费用。如果没有符合要求的行程，则返回 -1。

示例 1:

输入: n = 5, highways = [[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]], k = 3
输出: 17
解释:
一个可能的路径是从 0 -> 1 -> 4 -> 3。这次旅行的费用是 4 + 11 + 2 = 17。
另一种可能的路径是从 4 -> 1 -> 2 -> 3。这次旅行的费用是 11 + 3 + 3 = 17。
可以证明，17 是任何有效行程的最大可能费用。
注意，旅行 4 -> 1 -> 0 -> 1 是不允许的，因为你访问了城市 1 两次。

 

示例 2:

输入: n = 4, highways = [[0,1,3],[2,3,2]], k = 2
输出: -1
解释: 没有长度为 2 的有效行程，因此返回-1。

 

提示:

• 2 <= n <= 15
• 1 <= highways.length <= 50
• highways[i].length == 3
• 0 <= city1i, city2i <= n - 1
• city1i != city2i
• 0 <= tolli <= 100
• 1 <= k <= 50

• 没有重复的高速公路。

方法一：状态压缩动态规划 · Go 实现

思考

恰好走 $k$ 条边、城市不重复，求最大边权和。 $k\ge n$ 时边数已超过点数减一，必不可能。 $n\le 15$，适合用访问集合做状态。

令 $f[S][j]$ 为访问集合 $S$、停在 $j$ 的最大费用。单点出发为 $0$。枚举 $S$ 与终点 $j$，从 $j$ 的邻居 $h$ 转移： $f[S][j]\leftarrow f[S\setminus \{j\}][h]+\mathit{\text{cost}}(h,j)$。当 $|S|=k+1$ 时更新答案。

我们注意到，题目要求正好经过 $k$ 条公路，而每个城市最多只能访问一次，城市的数量为 $n$，因此，我们最多只能经过 $n-1$ 条公路。所以，如果 $k\ge n$，那么我们无法满足题目要求，直接返回 $-1$ 即可。

另外，我们也可以发现，城市数量 $n$ 不超过 $15$，这提示我们可以考虑使用状态压缩动态规划的方法求解本题。我们用一个长度为 $n$ 的二进制数表示当前已经经过的城市，其中第 $i$ 位为 $1$ 表示已经经过了第 $i$ 个城市，为 $0$ 表示还没有经过第 $i$ 个城市。

我们用 $f[i][j]$ 表示当前已经经过的城市为 $i$，最后一个经过的城市为 $j$ 的情况下，最大的旅行费用。初始时 $f[2^i][i]=0$，其余 $f[i][j]=-\mathrm{\infty }$。

考虑 $f[i][j]$ 如何进行状态转移。对于 $f[i]$，我们枚举所有城市 $j$，如果 $i$ 的第 $j$ 位为 $1$，那么我们就可以从其它城市 $h$ 经过公路到达城市 $j$，此时 $f[i][j]$ 的值为 $f[i][h]+cost(h,j)$ 的最大值，其中 $cost(h,j)$ 表示从城市 $h$ 到城市 $j$ 的旅行费用。因此，我们可以得到状态转移方程：

$$f[i][j]=\underset{h\in \mathit{\text{city}}}{max}\{f[i\mathrm{\setminus }j][h]+cost(h,j)\}$$

其中 $i\mathrm{\setminus }j$ 表示将 $i$ 的第 $j$ 位变为 $0$。

求出 $f[i][j]$ 后，我们判断经过的城市数量是否为 $k+1$，即 $i$ 的二进制表示中 $1$ 的个数是否为 $k+1$，如果是，那么我们就更新答案为 $ans=max(ans,f[i][j])$。

时间复杂度 $O(2^n\times n^2)$，空间复杂度 $O(2^n\times n)$。其中 $n$ 表示城市数量。

func maximumCost(n int, highways [][]int, k int) int {
	if k >= n {
		return -1
	}
	g := make([][][2]int, n)
	for _, h := range highways {
		a, b, cost := h[0], h[1], h[2]
		g[a] = append(g[a], [2]int{b, cost})
		g[b] = append(g[b], [2]int{a, cost})
	}
	f := make([][]int, 1<<n)
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = -(1 << 30)
		}
	}
	for i := 0; i < n; i++ {
		f[1<<i][i] = 0
	}
	ans := -1
	for i := 0; i < 1<<n; i++ {
		for j := 0; j < n; j++ {
			if i>>j&1 == 1 {
				for _, e := range g[j] {
					h, cost := e[0], e[1]
					if i>>h&1 == 1 {
						f[i][j] = max(f[i][j], f[i^(1<<j)][h]+cost)
					}
				}
			}
			if bits.OnesCount(uint(i)) == k+1 {
				ans = max(ans, f[i][j])
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2285. 道路的最大总重要性

中等1 种解法

标签：贪心、图、排序、堆（优先队列）

题目、示例与约束

给你一个整数 n ，表示一个国家里的城市数目。城市编号为 0 到 n - 1 。

给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] 表示城市 ai 和 bi 之间有一条 双向 道路。

你需要给每个城市安排一个从 1 到 n 之间的整数值，且每个值只能被使用 一次 。道路的 重要性 定义为这条道路连接的两座城市数值 之和 。

请你返回在最优安排下，所有道路重要性 之和 最大 为多少。

 

示例 1：

输入：n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
输出：43
解释：上图展示了国家图和每个城市被安排的值 [2,4,5,3,1] 。
- 道路 (0,1) 重要性为 2 + 4 = 6 。
- 道路 (1,2) 重要性为 4 + 5 = 9 。
- 道路 (2,3) 重要性为 5 + 3 = 8 。
- 道路 (0,2) 重要性为 2 + 5 = 7 。
- 道路 (1,3) 重要性为 4 + 3 = 7 。
- 道路 (2,4) 重要性为 5 + 1 = 6 。
所有道路重要性之和为 6 + 9 + 8 + 7 + 7 + 6 = 43 。
可以证明，重要性之和不可能超过 43 。

示例 2：

输入：n = 5, roads = [[0,3],[2,4],[1,3]]
输出：20
解释：上图展示了国家图和每个城市被安排的值 [4,3,2,5,1] 。
- 道路 (0,3) 重要性为 4 + 5 = 9 。
- 道路 (2,4) 重要性为 2 + 1 = 3 。
- 道路 (1,3) 重要性为 3 + 5 = 8 。
所有道路重要性之和为 9 + 3 + 8 = 20 。
可以证明，重要性之和不可能超过 20 。

 

提示：

• 2 <= n <= 5 * 104
• 1 <= roads.length <= 5 * 104
• roads[i].length == 2
• 0 <= ai, bi <= n - 1
• ai != bi
• 没有重复道路。

方法一：贪心 + 排序 · Go 实现

思考

给城市分配 $1$ 到 $n$ 的不同分值，一条边的重要性是两端之和，要求和最大。边的贡献等于两端分值之和，因此分值应与度数成正比：度数大的城市拿更大的编号。

统计度数，排序后与 $1..n$ 点乘。

我们考虑每个城市对所有道路的总重要性的贡献度，记录在数组 $\mathit{\text{deg}}$ 中。然后将 $\mathit{\text{deg}}$ 按贡献度从小到大排序，为城市依次分配 $[1,2,...,n]$。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。

func maximumImportance(n int, roads [][]int) (ans int64) {
	deg := make([]int, n)
	for _, r := range roads {
		deg[r[0]]++
		deg[r[1]]++
	}
	sort.Ints(deg)
	for i, x := range deg {
		ans += int64(x) * int64(i+1)
	}
	return
}

力扣原题 · Doocs 题解来源

2290. 到达角落需要移除障碍物的最小数目

困难1 种解法

标签：广度优先搜索、图、数组、矩阵、最短路、Dijkstra 算法、堆（优先队列）

题目、示例与约束

给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n 。每个单元格都是两个值之一：

• 0 表示一个 空 单元格，
• 1 表示一个可以移除的 障碍物 。

你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。

现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) ，返回需要移除的障碍物的 最小 数目。

 

示例 1：

输入：grid = [[0,1,1],[1,1,0],[1,1,0]]
输出：2
解释：可以移除位于 (0, 1) 和 (0, 2) 的障碍物来创建从 (0, 0) 到 (2, 2) 的路径。
可以证明我们至少需要移除两个障碍物，所以返回 2 。
注意，可能存在其他方式来移除 2 个障碍物，创建出可行的路径。

示例 2：

输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
输出：0
解释：不移除任何障碍物就能从 (0, 0) 到 (2, 4) ，所以返回 0 。

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 105
• 2 <= m * n <= 105
• grid[i][j] 为 0 或 1
• grid[0][0] == grid[m - 1][n - 1] == 0

方法一：双端队列 BFS · Go 实现

思考

从左上走到右下，进入障碍格算一次移除，求最少移除次数。 $mn\le {10}^5$，不能按障碍子集搜索。空地边权为 $0$、障碍边权为 $1$，这是 $0$-$1$ 最短路，可用双端队列 BFS。

走到空地时把新点放队首（代价不变），走到障碍时放队尾（代价加一）。首次到达终点即为最少移除。格子至多入队常数次。

本题实际上也是最短路模型，只不过求解的是移除障碍物的最小数目。

在一个边权只有 $0$, $1$ 的无向图中搜索最短路径可以使用双端队列进行 $BFS$。其原理是当前可以扩展到的点的权重为 $0$ 时，将其加入队首；权重为 $1$ 时，将其加入队尾。

如果某条边权值为 $0$，那么新拓展出的节点权值就和当前队首节点权值相同，显然可以作为下一次拓展的起点。

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

相似题目：

• 1368. 使网格图至少有一条有效路径的最小代价

func minimumObstacles(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	q := doublylinkedlist.New()
	type tuple struct{ i, j, k int }
	q.Add(tuple{0, 0, 0})
	vis := make([][]bool, m)
	for i := range vis {
		vis[i] = make([]bool, n)
	}
	dirs := [5]int{-1, 0, 1, 0, -1}
	for {
		v, _ := q.Get(0)
		p := v.(tuple)
		q.Remove(0)
		i, j, k := p.i, p.j, p.k
		if i == m-1 && j == n-1 {
			return k
		}
		if vis[i][j] {
			continue
		}
		vis[i][j] = true
		for h := 0; h < 4; h++ {
			x, y := i+dirs[h], j+dirs[h+1]
			if x >= 0 && x < m && y >= 0 && y < n {
				if grid[x][y] == 0 {
					q.Insert(0, tuple{x, y, k})
				} else {
					q.Add(tuple{x, y, k + 1})
				}
			}
		}
	}
}

力扣原题 · Doocs 题解来源

2297. 跳跃游戏 VIII 🔒

中等1 种解法

标签：栈、图、数组、动态规划、最短路、单调栈

题目、示例与约束

给定一个长度为 n 的下标从 0 开始的整数数组 nums。初始位置为下标 0。当 i < j 时，你可以从下标 i 跳转到下标 j:

• 对于在 i < k < j 范围内的所有下标 k 有 nums[i] <= nums[j] 和 nums[k] < nums[i] , 或者
• 对于在 i < k < j 范围内的所有下标 k 有 nums[i] > nums[j] 和 nums[k] >= nums[i] 。

你还得到了一个长度为 n 的整数数组 costs，其中 costs[i] 表示跳转到下标 i 的代价。

返回跳转到下标 n - 1 的最小代价。

示例 1:

输入: nums = [3,2,4,4,1], costs = [3,7,6,4,2]
输出: 8
解释: 从下标 0 开始。
- 以 costs[2]= 6 的代价跳转到下标 2。
- 以 costs[4]= 2 的代价跳转到下标 4。
总代价是 8。可以证明，8 是所需的最小代价。
另外两个可能的路径是:下标 0 -> 1 -> 4 和下标 0 -> 2 -> 3 -> 4。
它们的总代价分别为9和12。

示例 2:

输入: nums = [0,1,2], costs = [1,1,1]
输出: 2
解释: 从下标 0 开始。
- 以 costs[1] = 1 的代价跳转到下标 1。
- 以 costs[2] = 1 的代价跳转到下标 2。
总代价是 2。注意您不能直接从下标 0 跳转到下标 2，因为 nums[0] <= nums[1]。

 

解释:

• n == nums.length == costs.length
• 1 <= n <= 105
• 0 <= nums[i], costs[i] <= 105

方法一：单调栈 + 动态规划 · Go 实现

思考

从 $i$ 只能跳到「下一个 $\ge nums[i]$」或「下一个 $<nums[i]$」的位置，求到达终点的最小花费。 $n$ 较大时不能对每个 $i$ 向右扫描。这两个后继正是单调栈能在线性时间内求出的。

从右往左分别维护严格递增、非严格递减的栈，得到邻接表 $g[i]$。再按 $i$ 从小到大松弛 $f[j]=min(f[j],f[i]+costs[j])$。边数 $O(n)$，最短路即一遍 DP。

根据题目描述，我们实际上需要找到 $\mathit{\text{nums}}[i]$ 的下一个大于等于 $\mathit{\text{nums}}[i]$ 的位置 $j$，以及下一个小于 $\mathit{\text{nums}}[i]$ 的位置 $j$。我们利用单调栈可以在 $O(n)$ 的时间内找到这两个位置，然后构建邻接表 $g$，其中 $g[i]$ 表示下标 $i$ 可以跳转到的下标。

然后我们使用动态规划求解最小代价。设 $f[i]$ 表示跳转到下标 $i$ 的最小代价，初始时 $f[0]=0$，其余 $f[i]=\mathrm{\infty }$。我们从小到大枚举下标 $i$，对于每个 $i$，我们枚举 $g[i]$ 中的每个下标 $j$，进行状态转移 $f[j]=min(f[j],f[i]+\mathit{\text{costs}}[j])$。答案为 $f[n-1]$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组长度。

func minCost(nums []int, costs []int) int64 {
	n := len(nums)
	g := make([][]int, n)
	stk := []int{}
	for i := n - 1; i >= 0; i-- {
		for len(stk) > 0 && nums[stk[len(stk)-1]] < nums[i] {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			g[i] = append(g[i], stk[len(stk)-1])
		}
		stk = append(stk, i)
	}
	stk = []int{}
	for i := n - 1; i >= 0; i-- {
		for len(stk) > 0 && nums[stk[len(stk)-1]] >= nums[i] {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			g[i] = append(g[i], stk[len(stk)-1])
		}
		stk = append(stk, i)
	}
	f := make([]int64, n)
	for i := 1; i < n; i++ {
		f[i] = math.MaxInt64
	}
	for i := 0; i < n; i++ {
		for _, j := range g[i] {
			f[j] = min(f[j], f[i]+int64(costs[j]))
		}
	}
	return f[n-1]
}

力扣原题 · Doocs 题解来源

2328. 网格图中递增路径的数目

困难2 种解法

标签：深度优先搜索、广度优先搜索、图、拓扑排序、记忆化、数组、动态规划、矩阵

题目、示例与约束

给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。

请你返回在网格图中从 任意 格子出发，达到 任意 格子，且路径中的数字是 严格递增 的路径数目。由于答案可能会很大，请将结果对 109 + 7 取余 后返回。

如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。

 

示例 1：

输入：grid = [[1,1],[3,4]]
输出：8
解释：严格递增路径包括：
- 长度为 1 的路径：[1]，[1]，[3]，[4] 。
- 长度为 2 的路径：[1 -> 3]，[1 -> 4]，[3 -> 4] 。
- 长度为 3 的路径：[1 -> 3 -> 4] 。
路径数目为 4 + 3 + 1 = 8 。

示例 2：

输入：grid = [[1],[2]]
输出：3
解释：严格递增路径包括：
- 长度为 1 的路径：[1]，[2] 。
- 长度为 2 的路径：[1 -> 2] 。
路径数目为 2 + 1 = 3 。

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 1000
• 1 <= m * n <= 105
• 1 <= grid[i][j] <= 105

方法一：记忆化搜索 · Go 实现

思考

严格递增路径可从任意格出发、任意长度。网格至多 ${10}^5$ 格，枚举路径不可行。从一格出发的路径数只取决于能走到的更大邻居。

记忆化 $dfs(i,j)$：自身一条，加上四个严格更大邻居的方案。每个格子计算一次，总和即为全部路径数。

我们设计一个函数 $dfs(i,j)$，表示从网格图中的第 $i$ 行第 $j$ 列的格子出发，能够到达任意格子的严格递增路径数目。那么答案就是 $\sum _{i=0}^{m-1}\sum _{j=0}^{n-1}dfs(i,j)$。搜索过程中，我们可以用一个二维数组 $f$ 记录已经计算过的结果，避免重复计算。

函数 $dfs(i,j)$ 的计算过程如下：

• 如果 $f[i][j]$ 不为 $0$，说明已经计算过，直接返回 $f[i][j]$；
• 否则，我们初始化 $f[i][j]=1$，然后枚举 $(i,j)$ 的四个方向，如果某个方向的格子 $(x,y)$ 满足 $0\le x<m$, $0\le y<n$ 且 $grid[i][j]<grid[x][y]$，我们就可以从格子 $(i,j)$ 出发，到达格子 $(x,y)$，且路径上的数字是严格递增的，因此有 $f[i][j]+=dfs(x,y)$。

最后，我们返回 $f[i][j]$。

答案为 $\sum _{i=0}^{m-1}\sum _{j=0}^{n-1}dfs(i,j)$。

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

相似题目：

• 329. 矩阵中的最长递增路径。

func countPaths(grid [][]int) (ans int) {
	const mod = 1e9 + 7
	m, n := len(grid), len(grid[0])
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
	}
	var dfs func(int, int) int
	dfs = func(i, j int) int {
		if f[i][j] != 0 {
			return f[i][j]
		}
		f[i][j] = 1
		dirs := [5]int{-1, 0, 1, 0, -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[i][j] < grid[x][y] {
				f[i][j] = (f[i][j] + dfs(x, y)) % mod
			}
		}
		return f[i][j]
	}
	for i, row := range grid {
		for j := range row {
			ans = (ans + dfs(i, j)) % mod
		}
	}
	return
}

方法二：排序 + 动态规划 · Go 实现

思考

严格递增路径可从任意格出发。网格至多 ${10}^5$ 格。若从每个格子记忆化走向更大的邻居，一行严格递增的 $1000$ 个数就会把调用栈用尽，而 $m$ 和 $n$ 都可以到 $1000$。

瓶颈是这条递增链：每一步只进入尚未算完的更大邻居，深度与格子数同阶。

一格的方案数只依赖严格更大的邻居，这些边构成有向无环图。

因此按格子值从大到小处理。先令 $f[i][j]=1$，再把四个更大邻居已经算完的方案数加进来，并对 ${10}^9+7$ 取模。全部 $f$ 之和再取模，就是从任意格出发的路径总数。

令 $f[i][j]$ 表示从第 $i$ 行第 $j$ 列出发的严格递增路径数。一格至少有一条只含自己的路径，所以初值为 $1$。它还能走向四个方向上严格更大的邻居，因此

$$f[i][j]=1+\sum _{\begin{array}{c}(x,y)\sim (i,j)\\ grid[i][j]<grid[x][y]\end{array}}f[x][y](\mathrm{mod}{10}^9+7).$$

值更大的格子不依赖当前格子，按 $grid$ 从大到小处理时，这些 $f[x][y]$ 已经就绪。答案为 $\sum f[i][j]$ 对 ${10}^9+7$ 取模。

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

相似题目：

• 329. 矩阵中的最长递增路径。

func countPaths(grid [][]int) int {
	const mod = 1e9 + 7
	m, n := len(grid), len(grid[0])
	f := make([][]int, m)
	cells := make([][3]int, 0, m*n)
	for i := 0; i < m; i++ {
		f[i] = make([]int, n)
		for j := 0; j < n; j++ {
			f[i][j] = 1
			cells = append(cells, [3]int{grid[i][j], i, j})
		}
	}
	sort.Slice(cells, func(a, b int) bool { return cells[a][0] > cells[b][0] })
	dirs := [5]int{-1, 0, 1, 0, -1}
	for _, cell := range cells {
		i, j := cell[1], cell[2]
		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[i][j] < grid[x][y] {
				f[i][j] = (f[i][j] + f[x][y]) % mod
			}
		}
	}
	ans := 0
	for _, row := range f {
		for _, v := range row {
			ans = (ans + v) % mod
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2359. 找到离给定两个节点最近的节点

中等1 种解法

标签：深度优先搜索、图

题目、示例与约束

给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。

有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。

同时给你两个节点 node1 和 node2 。

请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 -1 。

注意 edges 可能包含环。

 

示例 1：

输入：edges = [2,2,3,-1], node1 = 0, node2 = 1
输出：2
解释：从节点 0 到节点 2 的距离为 1 ，从节点 1 到节点 2 的距离为 1 。
两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值，所以我们返回节点 2 。

示例 2：

输入：edges = [1,2,-1], node1 = 0, node2 = 2
输出：2
解释：节点 0 到节点 2 的距离为 2 ，节点 2 到它自己的距离为 0 。
两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值，所以我们返回节点 2 。

 

提示：

• n == edges.length
• 2 <= n <= 105
• -1 <= edges[i] < n
• edges[i] != i
• 0 <= node1, node2 < n

方法一：BFS + 枚举公共点 · Go 实现

思考

每个点出度至多 $1$，从 $node1$、 $node2$ 出发的可达点构成两条链（或环上的一段）。 $n\le {10}^5$，适合各做一次 BFS。

求出两份距离后枚举每个公共点，最小化 $max(d_1[i],d_2[i])$，并列取更小编号。不可达保持无穷大。

我们可以先用 BFS 求出从 $node1$ 和 $node2$ 分别到达每个点的距离，分别记为 $d_1$ 和 $d_2$。然后枚举所有的公共点 $i$，然后求出 $max(d_1[i],d_2[i])$，取其中的最小值即可。

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

相似题目：

• 2203.得到要求路径的最小带权子图

func closestMeetingNode(edges []int, node1 int, node2 int) int {
	n := len(edges)
	g := make([][]int, n)
	for i, j := range edges {
		if j != -1 {
			g[i] = append(g[i], j)
		}
	}
	const inf int = 1 << 30
	f := func(i int) []int {
		dist := make([]int, n)
		for j := range dist {
			dist[j] = inf
		}
		dist[i] = 0
		q := []int{i}
		for len(q) > 0 {
			i = q[0]
			q = q[1:]
			for _, j := range g[i] {
				if dist[j] == inf {
					dist[j] = dist[i] + 1
					q = append(q, j)
				}
			}
		}
		return dist
	}
	d1 := f(node1)
	d2 := f(node2)
	ans, d := -1, inf
	for i, a := range d1 {
		b := d2[i]
		t := max(a, b)
		if t < d {
			d = t
			ans = i
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2360. 图中的最长环

困难1 种解法

标签：深度优先搜索、广度优先搜索、图、拓扑排序、Kosaraju 算法、Tarjan 强连通分量算法

题目、示例与约束

给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，其中每个节点 至多 有一条出边。

图用一个大小为 n 下标从 0 开始的数组 edges 表示，节点 i 到节点 edges[i] 之间有一条有向边。如果节点 i 没有出边，那么 edges[i] == -1 。

请你返回图中的 最长 环，如果没有任何环，请返回 -1 。

一个环指的是起点和终点是 同一个 节点的路径。

 

示例 1：

输入：edges = [3,3,4,2,3]
输出去：3
解释：图中的最长环是：2 -> 4 -> 3 -> 2 。
这个环的长度为 3 ，所以返回 3 。

示例 2：

输入：edges = [2,-1,3,1]
输出：-1
解释：图中没有任何环。

 

提示：

• n == edges.length
• 2 <= n <= 105
• -1 <= edges[i] < n
• edges[i] != i

方法一：遍历出发点 · Go 实现

思考

每个点至多一条出边，图由链指向环组成。 $n\le {10}^5$，从每个未访点沿唯一后继走即可。

沿途标记访问并记下路径。若停在未定义后继则无环；若停在本路径中的点，则从该点到路径末尾即一环，用其长度更新答案。

我们可以遍历 $[0,..,n-1]$ 范围内的每个节点，如果该节点未被访问过，则从该节点出发，搜索邻边节点，直到遇到环或者遇到已经访问过的节点。如果遇到环，则更新答案。

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

相似题目：

• 2127. 参加会议的最多员工数

func longestCycle(edges []int) int {
	vis := make([]bool, len(edges))
	ans := -1
	for i := range edges {
		if vis[i] {
			continue
		}
		j := i
		cycle := []int{}
		for ; j != -1 && !vis[j]; j = edges[j] {
			vis[j] = true
			cycle = append(cycle, j)
		}
		if j == -1 {
			continue
		}
		for k := range cycle {
			if cycle[k] == j {
				ans = max(ans, len(cycle)-k)
				break
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2374. 边积分最高的节点

中等1 种解法

标签：图、哈希表

题目、示例与约束

给你一个有向图，图中有 n 个节点，节点编号从 0 到 n - 1 ，其中每个节点都 恰有一条 出边。

图由一个下标从 0 开始、长度为 n 的整数数组 edges 表示，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的 有向 边。

节点 i 的 边积分 定义为：所有存在一条指向节点 i 的边的节点的 编号 总和。

返回 边积分 最高的节点。如果多个节点的 边积分 相同，返回编号 最小 的那个。

 

示例 1：

输入：edges = [1,0,0,0,0,7,7,5]
输出：7
解释：
- 节点 1、2、3 和 4 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 + 3 + 4 = 10 。
- 节点 0 有一条指向节点 1 的边，节点 1 的边积分等于 0 。
- 节点 7 有一条指向节点 5 的边，节点 5 的边积分等于 7 。
- 节点 5 和 6 都有指向节点 7 的边，节点 7 的边积分等于 5 + 6 = 11 。
节点 7 的边积分最高，所以返回 7 。

示例 2：

输入：edges = [2,0,0,2]
输出：0
解释：
- 节点 1 和 2 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 = 3 。
- 节点 0 和 3 都有指向节点 2 的边，节点 2 的边积分等于 0 + 3 = 3 。
节点 0 和 2 的边积分都是 3 。由于节点 0 的编号更小，返回 0 。

 

提示：

• n == edges.length
• 2 <= n <= 105
• 0 <= edges[i] < n
• edges[i] != i

方法一：一次遍历 · Go 实现

思考

边积分是指向该点的下标之和。 $n\le {10}^5$，一次累加即可，并列取较小编号。

数组 $cnt[j]$ 加上来源 $i$。边走边与当前最优比较，避免第二遍扫描。

我们定义一个长度为 $n$ 的数组 $\mathit{\text{cnt}}$，其中 $\mathit{\text{cnt}}[i]$ 表示节点 $i$ 的边积分，初始时所有元素均为 $0$。定义一个答案变量 $\mathit{\text{ans}}$，初始时为 $0$。

接下来，我们遍历数组 $\mathit{\text{edges}}$，对于每个节点 $i$，以及它的出边节点 $j$，我们更新 $\mathit{\text{cnt}}[j]$ 为 $\mathit{\text{cnt}}[j]+i$。如果 $\mathit{\text{cnt}}[\mathit{\text{ans}}]<\mathit{\text{cnt}}[j]$ 或者 $\mathit{\text{cnt}}[\mathit{\text{ans}}]=\mathit{\text{cnt}}[j]$ 且 $j<\mathit{\text{ans}}$，我们更新 $\mathit{\text{ans}}$ 为 $j$。

最后，返回 $\mathit{\text{ans}}$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\mathit{\text{edges}}$ 的长度。

func edgeScore(edges []int) (ans int) {
	cnt := make([]int, len(edges))
	for i, j := range edges {
		cnt[j] += i
		if cnt[ans] < cnt[j] || (cnt[ans] == cnt[j] && j < ans) {
			ans = j
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2392. 给定条件下构造矩阵

困难1 种解法

标签：图、拓扑排序、数组、有向无环图、矩阵

题目、示例与约束

给你一个 正 整数 k ，同时给你：

• 一个大小为 n 的二维整数数组 rowConditions ，其中 rowConditions[i] = [abovei, belowi] 和
• 一个大小为 m 的二维整数数组 colConditions ，其中 colConditions[i] = [lefti, righti] 。

两个数组里的整数都是 1 到 k 之间的数字。

你需要构造一个 k x k 的矩阵，1 到 k 每个数字需要 恰好出现一次 。剩余的数字都是 0 。

矩阵还需要满足以下条件：

• 对于所有 0 到 n - 1 之间的下标 i ，数字 abovei 所在的 行 必须在数字 belowi 所在行的上面。
• 对于所有 0 到 m - 1 之间的下标 i ，数字 lefti 所在的 列 必须在数字 righti 所在列的左边。

返回满足上述要求的 任意 矩阵。如果不存在答案，返回一个空的矩阵。

 

示例 1：

输入：k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
输出：[[3,0,0],[0,0,1],[0,2,0]]
解释：上图为一个符合所有条件的矩阵。
行要求如下：
- 数字 1 在第 1 行，数字 2 在第 2 行，1 在 2 的上面。
- 数字 3 在第 0 行，数字 2 在第 2 行，3 在 2 的上面。
列要求如下：
- 数字 2 在第 1 列，数字 1 在第 2 列，2 在 1 的左边。
- 数字 3 在第 0 列，数字 2 在第 1 列，3 在 2 的左边。
注意，可能有多种正确的答案。

示例 2：

输入：k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
输出：[]
解释：由前两个条件可以得到 3 在 1 的下面，但第三个条件是 3 在 1 的上面。
没有符合条件的矩阵存在，所以我们返回空矩阵。

 

提示：

• 2 <= k <= 400
• 1 <= rowConditions.length, colConditions.length <= 104
• rowConditions[i].length == colConditions[i].length == 2
• 1 <= abovei, belowi, lefti, righti <= k
• abovei != belowi
• lefti != righti

方法一：拓扑排序 · Go 实现

思考

$1..k$ 各出现一次，行约束与列约束给出先后。 $k\le 400$，把先后看成有向边后做拓扑排序。若有环则无解。

对行条件、列条件分别拓扑得到两个排列，再按下标写入矩阵。某一维无法排出 $k$ 个点即返回空。

利用拓扑排序，找到一个合法的 row 序列和 col 序列，然后根据这两个序列构造出矩阵。

时间复杂度 $O(m+n+k)$。其中 $m$ 和 $n$ 分别为 rowConditions 和 colConditions 的长度，而 $k$ 为题目中给定的正整数。

func buildMatrix(k int, rowConditions [][]int, colConditions [][]int) [][]int {
	f := func(cond [][]int) []int {
		g := make([][]int, k+1)
		indeg := make([]int, k+1)
		for _, e := range cond {
			a, b := e[0], e[1]
			g[a] = append(g[a], b)
			indeg[b]++
		}
		q := []int{}
		for i, v := range indeg[1:] {
			if v == 0 {
				q = append(q, i+1)
			}
		}
		res := []int{}
		for len(q) > 0 {
			for n := len(q); n > 0; n-- {
				i := q[0]
				q = q[1:]
				res = append(res, i)
				for _, j := range g[i] {
					indeg[j]--
					if indeg[j] == 0 {
						q = append(q, j)
					}
				}
			}
		}
		if len(res) == k {
			return res
		}
		return []int{}
	}

	row := f(rowConditions)
	col := f(colConditions)
	if len(row) == 0 || len(col) == 0 {
		return [][]int{}
	}
	m := make([]int, k+1)
	for i, v := range col {
		m[v] = i
	}
	ans := make([][]int, k)
	for i := range ans {
		ans[i] = make([]int, k)
	}
	for i, v := range row {
		ans[i][m[v]] = v
	}
	return ans
}

力扣原题 · Doocs 题解来源

2467. 树上最大得分和路径

中等2 种解法

标签：树、深度优先搜索、广度优先搜索、图、数组

题目、示例与约束

一个 n 个节点的无向树，节点编号为 0 到 n - 1 ，树的根结点是 0 号节点。给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] ，表示节点 ai 和 bi 在树中有一条边。

在每一个节点 i 处有一扇门。同时给你一个都是偶数的数组 amount ，其中 amount[i] 表示：

• 如果 amount[i] 的值是负数，那么它表示打开节点 i 处门扣除的分数。
• 如果 amount[i] 的值是正数，那么它表示打开节点 i 处门加上的分数。

游戏按照如下规则进行：

• 一开始，Alice 在节点 0 处，Bob 在节点 bob 处。
• 每一秒钟，Alice 和 Bob 分别 移动到相邻的节点。Alice 朝着某个 叶子结点 移动，Bob 朝着节点 0 移动。
• 对于他们之间路径上的 每一个 节点，Alice 和 Bob 要么打开门并扣分，要么打开门并加分。注意：
  • 如果门 已经打开 （被另一个人打开），不会有额外加分也不会扣分。
  • 如果 Alice 和 Bob 同时 到达一个节点，他们会共享这个节点的加分或者扣分。换言之，如果打开这扇门扣 c 分，那么 Alice 和 Bob 分别扣 c / 2 分。如果这扇门的加分为 c ，那么他们分别加 c / 2 分。
• 如果 Alice 到达了一个叶子结点，她会停止移动。类似的，如果 Bob 到达了节点 0 ，他也会停止移动。注意这些事件互相 独立 ，不会影响另一方移动。

请你返回 Alice 朝最优叶子结点移动的 最大 净得分。

 

示例 1：

输入：edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]
输出：6
解释：
上图展示了输入给出的一棵树。游戏进行如下：
- Alice 一开始在节点 0 处，Bob 在节点 3 处。他们分别打开所在节点的门。
  Alice 得分为 -2 。
- Alice 和 Bob 都移动到节点 1 。
  因为他们同时到达这个节点，他们一起打开门并平分得分。
  Alice 的得分变为 -2 + (4 / 2) = 0 。
- Alice 移动到节点 3 。因为 Bob 已经打开了这扇门，Alice 得分不变。
  Bob 移动到节点 0 ，并停止移动。
- Alice 移动到节点 4 并打开这个节点的门，她得分变为 0 + 6 = 6 。
现在，Alice 和 Bob 都不能进行任何移动了，所以游戏结束。
Alice 无法得到更高分数。

示例 2：

输入：edges = [[0,1]], bob = 1, amount = [-7280,2350]
输出：-7280
解释：
Alice 按照路径 0->1 移动，同时 Bob 按照路径 1->0 移动。
所以 Alice 只打开节点 0 处的门，她的得分为 -7280 。

 

提示：

• 2 <= n <= 105
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• edges 表示一棵有效的树。
• 1 <= bob < n
• amount.length == n
• amount[i] 是范围 [-104, 104] 之间的一个 偶数 。

方法一：两次 DFS · Go 实现

思考

Bob 的路线固定为 $bob\to 0$，Alice 从 $0$ 走向某一叶子。 $n\le {10}^5$，先 DFS 记下 Bob 到达各点的时间 $ts$。

再从 $0$ 出发 DFS：到达时刻等于 $ts[i]$ 则平分收益，更早则独得，更晚则门已空。在叶子更新最大得分。

根据题意，我们可以知道，Bob 的移动路径是固定的，即从节点 $bob$ 出发，最终到达节点 $0$。因此，我们可以先跑一遍 DFS，求出 Bob 到达每个节点的时间，记在数组 $ts$ 中。

然后我们再跑一遍 DFS，求出 Alice 每条移动路径的最大得分，我们记 Alice 到达节点 $i$ 的时间为 $t$，当前累计得分为 $v$，那么 Alice 在经过节点 $i$ 处后，累计的分数有三种情况：

1. Alice 到达节点 $i$ 的时间 $t$ 与 Bob 到达节点 $i$ 的时间 $ts[i]$ 相同，那么 Alice 和 Bob 同时打开节点 $i$ 处的门，Alice 获得的分数为 $v+\frac{amount[i]}{2}$；
2. Alice 到达节点 $i$ 的时间 $t$ 小于 Bob 到达节点 $i$ 的时间 $ts[i]$，那么 Alice 打开节点 $i$ 处的门，Alice 获得的分数为 $v+amount[i]$。
3. Alice 到达节点 $i$ 的时间 $t$ 大于 Bob 到达节点 $i$ 的时间 $ts[i]$，那么 Alice 不打开节点 $i$ 处的门，Alice 获得的分数为 $v$，即不变。

当 Alice 到达叶子节点时，更新最大得分。

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

func mostProfitablePath(edges [][]int, bob int, amount []int) int {
	n := len(edges) + 1
	g := make([][]int, n)
	for _, e := range edges {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	ts := make([]int, n)
	for i := range ts {
		ts[i] = n
	}
	var dfs1 func(int, int, int) bool
	dfs1 = func(i, fa, t int) bool {
		if i == 0 {
			ts[i] = min(ts[i], t)
			return true
		}
		for _, j := range g[i] {
			if j != fa && dfs1(j, i, t+1) {
				ts[j] = min(ts[j], t+1)
				return true
			}
		}
		return false
	}
	dfs1(bob, -1, 0)
	ts[bob] = 0
	ans := -0x3f3f3f3f
	var dfs2 func(int, int, int, int)
	dfs2 = func(i, fa, t, v int) {
		if t == ts[i] {
			v += amount[i] >> 1
		} else if t < ts[i] {
			v += amount[i]
		}
		if len(g[i]) == 1 && g[i][0] == fa {
			ans = max(ans, v)
			return
		}
		for _, j := range g[i] {
			if j != fa {
				dfs2(j, i, t+1, v)
			}
		}
	}
	dfs2(0, -1, 0, 0)
	return ans
}

方法二：两次显式栈 · Go 实现

思考

Bob 的路线是树上从 $bob$ 到根 $0$ 的唯一路径，Alice 从 $0$ 走向某个叶子，答案取她的最大净收入。 $n\le {10}^5$，沿一条链递归时调用深度等于节点数，链长达到 $1000$ 就会超出 Python 的递归上限。路径唯一，不必在搜索中层层返回：先用栈从 $0$ 记下父亲，再顺着父亲把 Bob 的到达时间写入 $ts$，其余节点保持哨兵 $n$。Alice 在节点 $i$ 的得分只取决于她的时刻 $t$ 与 $ts[i]$ 的先后，第二遍用栈做前序。弹出时按同时、更早、更晚累加收益，仅当该点只与父亲相邻时才把它当作叶子并更新答案。

树上从 $bob$ 到 $0$ 只有一条路径。用显式栈从节点 $0$ 遍历整棵树，记录每个节点的父亲。然后从 $bob$ 沿着父亲走到 $0$，第 $t$ 步到达的节点把 $ts$ 设为 $t$。没有走到的节点保持初值 $n$，表示 Bob 不会经过。

接着用显式栈模拟 Alice 从 $0$ 走向叶子。栈里存放节点、父亲、到达时刻 $t$ 和进入该节点前的累计得分 $v$。弹出节点 $i$ 后，累计得分有三种情况：

1. Alice 到达节点 $i$ 的时间 $t$ 与 Bob 到达节点 $i$ 的时间 $ts[i]$ 相同，那么 Alice 和 Bob 同时打开节点 $i$ 处的门，Alice 获得的分数为 $v+\frac{amount[i]}{2}$；
2. Alice 到达节点 $i$ 的时间 $t$ 小于 Bob 到达节点 $i$ 的时间 $ts[i]$，那么 Alice 打开节点 $i$ 处的门，Alice 获得的分数为 $v+amount[i]$。
3. Alice 到达节点 $i$ 的时间 $t$ 大于 Bob 到达节点 $i$ 的时间 $ts[i]$，那么 Alice 不打开节点 $i$ 处的门，Alice 获得的分数为 $v$，即不变。

若 $i$ 只有一个邻居且该邻居是父亲，则 $i$ 是叶子，用当前得分更新答案。

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

func mostProfitablePath(edges [][]int, bob int, amount []int) int {
	n := len(edges) + 1
	g := make([][]int, n)
	for _, e := range edges {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	parent := make([]int, n)
	for i := range parent {
		parent[i] = -1
	}
	seen := make([]bool, n)
	seen[0] = true
	stk := []int{0}
	for len(stk) > 0 {
		i := stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		for _, j := range g[i] {
			if !seen[j] {
				seen[j] = true
				parent[j] = i
				stk = append(stk, j)
			}
		}
	}
	ts := make([]int, n)
	for i := range ts {
		ts[i] = n
	}
	for x, t := bob, 0; x != -1; x, t = parent[x], t+1 {
		ts[x] = t
	}
	ans := -0x3f3f3f3f
	type frame struct{ i, fa, t, v int }
	walk := []frame{{0, -1, 0, 0}}
	for len(walk) > 0 {
		f := walk[len(walk)-1]
		walk = walk[:len(walk)-1]
		v := f.v
		if f.t == ts[f.i] {
			v += amount[f.i] >> 1
		} else if f.t < ts[f.i] {
			v += amount[f.i]
		}
		if len(g[f.i]) == 1 && g[f.i][0] == f.fa {
			ans = max(ans, v)
			continue
		}
		for _, j := range g[f.i] {
			if j != f.fa {
				walk = append(walk, frame{j, f.i, f.t + 1, v})
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2473. 购买苹果的最低成本 🔒

中等1 种解法

标签：图、数组、最短路、堆（优先队列）

题目、示例与约束

给你一个正整数  n，表示从 1 到 n 的 n 个城市。还给你一个 二维 数组 roads，其中 roads[i] = [ai, bi, costi] 表示在城市 ai 和 bi 之间有一条双向道路，其旅行成本等于 costi。

你可以在 任何 城市买到苹果，但是有些城市买苹果的费用不同。给定数组 appleCost ，其中 appleCost[i] 是从城市 i 购买一个苹果的成本。

你从某个城市开始，穿越各种道路，最终从 任何一个 城市买 一个 苹果。在你买了那个苹果之后，你必须回到你 开始的 城市，但现在所有道路的成本将 乘以 一个给定的因子 k。

给定整数 k，返回一个大小为 n 的从 1 开始的数组 answer，其中 answer[i] 是从城市 i 开始购买一个苹果的 最小 总成本。

 

示例 1:

输入: n = 4, roads = [[1,2,4],[2,3,2],[2,4,5],[3,4,1],[1,3,4]], appleCost = [56,42,102,301], k = 2
输出: [54,42,48,51]
解释: 每个起始城市的最低费用如下:
- 从城市 1 开始:你走路径 1 -> 2，在城市 2 买一个苹果，最后走路径 2 -> 1。总成本是 4 + 42 + 4 * 2 = 54。
- 从城市 2 开始:你直接在城市 2 买一个苹果。总费用是 42。
- 从城市 3 开始:你走路径 3 -> 2，在城市 2 买一个苹果，最后走路径 2 -> 3。总成本是 2 + 42 + 2 * 2 = 48。
- 从城市 4 开始:你走路径 4 -> 3 -> 2，然后你在城市 2 购买，最后走路径 2 -> 3 -> 4。总成本是 1 + 2 + 42 + 1 * 2 + 2 * 2 = 51。

示例 2:

输入: n = 3, roads = [[1,2,5],[2,3,1],[3,1,2]], appleCost = [2,3,1], k = 3
输出: [2,3,1]
解释: 在起始城市买苹果总是最优的。

 

提示:

• 2 <= n <= 1000
• 1 <= roads.length <= 1000
• 1 <= ai, bi <= n
• ai != bi
• 1 <= costi <= 105
• appleCost.length == n
• 1 <= appleCost[i] <= 105
• 1 <= k <= 100

• 没有重复的边。

方法一：堆优化版 Dijkstra 算法 · Go 实现

思考

可在任一城市买苹果，回家路费按 $(k+1)$ 倍计（去程每条边还要付 $k$ 的返程加成）。对每个起点做一次最短路，途中用 $\mathit{\text{appleCost}}[u]+dist[u]\cdot (k+1)$ 更新该起点的最优买法。

堆优化 Dijkstra 在稀疏图上为 $O(m\log n)$，对每个起点各跑一次。

我们枚举起点，对于每个起点，使用 Dijkstra 算法求出到其他所有点的最短距离，更新最小值即可。

时间复杂度 $O(n\times m\times \log m)$，其中 $n$ 和 $m$ 分别是城市数量和道路数量。

func minCost(n int, roads [][]int, appleCost []int, k int) []int64 {
	g := make([]pairs, n)
	for _, e := range roads {
		a, b, c := e[0]-1, e[1]-1, e[2]
		g[a] = append(g[a], pair{b, c})
		g[b] = append(g[b], pair{a, c})
	}
	const inf int = 0x3f3f3f3f
	dist := make([]int, n)
	dijkstra := func(u int) int64 {
		var ans int64 = math.MaxInt64
		for i := range dist {
			dist[i] = inf
		}
		dist[u] = 0
		q := make(pairs, 0)
		heap.Push(&q, pair{0, u})
		for len(q) > 0 {
			p := heap.Pop(&q).(pair)
			d := p.first
			u = p.second
			ans = min(ans, int64(appleCost[u]+d*(k+1)))
			for _, ne := range g[u] {
				v, w := ne.first, ne.second
				if dist[v] > dist[u]+w {
					dist[v] = dist[u] + w
					heap.Push(&q, pair{dist[v], v})
				}
			}
		}
		return ans
	}
	ans := make([]int64, n)
	for i := range ans {
		ans[i] = dijkstra(i)
	}
	return ans
}

type pair struct{ first, second int }

var _ heap.Interface = (*pairs)(nil)

type pairs []pair

func (a pairs) Len() int { return len(a) }
func (a pairs) Less(i int, j int) bool {
	return a[i].first < a[j].first || a[i].first == a[j].first && a[i].second < a[j].second
}
func (a pairs) Swap(i int, j int) { a[i], a[j] = a[j], a[i] }
func (a *pairs) Push(x any)       { *a = append(*a, x.(pair)) }
func (a *pairs) Pop() any         { l := len(*a); t := (*a)[l-1]; *a = (*a)[:l-1]; return t }

力扣原题 · Doocs 题解来源

2477. 到达首都的最少油耗

中等2 种解法

标签：树、深度优先搜索、广度优先搜索、图

题目、示例与约束

给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条 双向路 。

每个城市里有一个代表，他们都要去首都参加一个会议。

每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。

城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。

请你返回到达首都最少需要多少升汽油。

 

示例 1：

输入：roads = [[0,1],[0,2],[0,3]], seats = 5
输出：3
解释：
- 代表 1 直接到达首都，消耗 1 升汽油。
- 代表 2 直接到达首都，消耗 1 升汽油。
- 代表 3 直接到达首都，消耗 1 升汽油。
最少消耗 3 升汽油。

示例 2：

输入：roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
输出：7
解释：
- 代表 2 到达城市 3 ，消耗 1 升汽油。
- 代表 2 和代表 3 一起到达城市 1 ，消耗 1 升汽油。
- 代表 2 和代表 3 一起到达首都，消耗 1 升汽油。
- 代表 1 直接到达首都，消耗 1 升汽油。
- 代表 5 直接到达首都，消耗 1 升汽油。
- 代表 6 到达城市 4 ，消耗 1 升汽油。
- 代表 4 和代表 6 一起到达首都，消耗 1 升汽油。
最少消耗 7 升汽油。

示例 3：

输入：roads = [], seats = 1
输出：0
解释：没有代表需要从别的城市到达首都。

 

提示：

• 1 <= n <= 105
• roads.length == n - 1
• roads[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• roads 表示一棵合法的树。
• 1 <= seats <= 105

方法一：贪心 + DFS · Go 实现

思考

所有人最终到首都，车只向根行驶。 $n\le {10}^5$，子树 $sz$ 人从孩子走到当前节点至少需要 $\lceil sz/seats\rceil$ 升油，且应在子树内尽量拼车。

自底向上 DFS：孩子子树大小为 $t$ 时，边油耗加 $\lceil t/seats\rceil$，并累加到本子树人数。根无需再向上。

根据题目描述，我们可以发现，所有车只会往首都（节点 $0$）开。

假设有一个节点 $a$，它的下一个节点为 $b$，节点 $a$ 需要经过节点 $b$ 才能到达首都。为了使得节点 $a$ 的车辆（油耗）尽可能少，我们应该贪心地让节点 $a$ 的子节点先汇聚到节点 $a$，然后按照座位数 $seats$ 分配车辆，那么到达节点 $b$ 需要的最少车辆（油耗）就是 $\lceil \frac{sz}{seats}\rceil$。其中 $sz$ 表示以节点 $a$ 为根的子树的节点数。

我们从节点 $0$ 开始进行深度优先搜索，用一个变量 $sz$ 统计以当前节点为根节点的子树的节点数。初始时 $sz=1$，表示当前节点本身。然后我们遍历当前节点的所有子节点，对于每个子节点 $b$，我们递归地计算以 $b$ 为根节点的子树的节点数 $t$，并将 $t$ 累加到 $sz$ 上，然后我们将 $\lceil \frac{t}{seats}\rceil$ 累加到答案上。最后返回 $sz$。

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

func minimumFuelCost(roads [][]int, seats int) (ans int64) {
	n := len(roads) + 1
	g := make([][]int, n)
	for _, e := range roads {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	var dfs func(int, int) int
	dfs = func(a, fa int) int {
		sz := 1
		for _, b := range g[a] {
			if b != fa {
				t := dfs(b, a)
				ans += int64((t + seats - 1) / seats)
				sz += t
			}
		}
		return sz
	}
	dfs(0, -1)
	return
}

方法二：贪心 + 显式栈 · Go 实现

思考

所有人最终到首都，车只向根行驶。 $n$ 可以到 ${10}^5$。一条链上第一次递归总是走向唯一的孩子，深度就是 $n$，会超出默认递归上限。

每条边的油耗只由孩子子树的人数决定，必须先知道孩子再算父亲。

因此用显式栈做后序：进入节点时先压入离开标记，再压入子节点。离开时孩子的人数已经写好，边油耗加上 $\lceil t/seats\rceil$，并累加到本节点。根没有向上的边。

根据题目描述，我们可以发现，所有车只会往首都（节点 $0$）开。

假设有一个节点 $a$，它的下一个节点为 $b$，节点 $a$ 需要经过节点 $b$ 才能到达首都。为了使得节点 $a$ 的车辆（油耗）尽可能少，我们应该贪心地让节点 $a$ 的子节点先汇聚到节点 $a$，然后按照座位数 $seats$ 分配车辆，那么到达节点 $b$ 需要的最少车辆（油耗）就是 $\lceil \frac{sz}{seats}\rceil$。其中 $sz$ 表示以节点 $a$ 为根的子树的节点数。

用显式栈从节点 $0$ 做后序遍历。进入一个节点时，先压入该节点的离开标记，再压入它的子节点，这样子节点会先处理完。离开时，子节点 $b$ 的子树人数 $t$ 已经确定，把 $\lceil t/seats\rceil$ 累加到答案，并把 $t$ 加进当前节点的人数。当前节点自身最初算 $1$ 个人。根节点没有再向上的边。

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

func minimumFuelCost(roads [][]int, seats int) (ans int64) {
	n := len(roads) + 1
	g := make([][]int, n)
	for _, e := range roads {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	sz := make([]int, n)
	for i := range sz {
		sz[i] = 1
	}
	stk := [][3]int{{0, -1, 0}}
	for len(stk) > 0 {
		cur := stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		a, fa, state := cur[0], cur[1], cur[2]
		if state == 0 {
			stk = append(stk, [3]int{a, fa, 1})
			for _, b := range g[a] {
				if b != fa {
					stk = append(stk, [3]int{b, a, 0})
				}
			}
		} else {
			for _, b := range g[a] {
				if b != fa {
					t := sz[b]
					ans += int64((t + seats - 1) / seats)
					sz[a] += t
				}
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2497. 图中最大星和

中等1 种解法

标签：贪心、图、数组、排序、堆（优先队列）

题目、示例与约束

给你一个 n 个点的无向图，节点从 0 到 n - 1 编号。给你一个长度为 n 下标从 0 开始的整数数组 vals ，其中 vals[i] 表示第 i 个节点的值。

同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条双向边。

星图 是给定图中的一个子图，它包含一个中心节点和 0 个或更多个邻居。换言之，星图是给定图中一个边的子集，且这些边都有一个公共节点。

下图分别展示了有 3 个和 4 个邻居的星图，蓝色节点为中心节点。

星和 定义为星图中所有节点值的和。

给你一个整数 k ，请你返回 至多 包含 k 条边的星图中的 最大星和 。

 

示例 1：

输入：vals = [1,2,3,4,10,-10,-20], edges = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]], k = 2
输出：16
解释：上图展示了输入示例。
最大星和对应的星图在上图中用蓝色标出。中心节点是 3 ，星图中还包含邻居 1 和 4 。
无法得到一个和大于 16 且边数不超过 2 的星图。

示例 2：

输入：vals = [-5], edges = [], k = 0
输出：-5
解释：只有一个星图，就是节点 0 自己。
所以我们返回 -5 。

 

提示：

• n == vals.length
• 1 <= n <= 105
• -104 <= vals[i] <= 104
• 0 <= edges.length <= min(n * (n - 1) / 2, 105)
• edges[i].length == 2
• 0 <= ai, bi <= n - 1
• ai != bi
• 0 <= k <= n - 1

方法一：排序 + 模拟 · Go 实现

思考

星图是中心加至多 $k$ 条边。负权邻居不必选。 $n\le {10}^5$，把正权邻居按降序排序，每个中心取前 $k$ 个之和加自身，再在所有中心上取最大。

我们先将输入的边集合转换成邻接表，其中 $g[i]$ 表示节点 $i$ 的邻居节点的值列表，且按照值的降序排列。

然后我们遍历每个节点 $i$，计算以 $i$ 为中心节点的星图的最大星和，即 $vals[i]+\sum _{j=0}^{k-1}g[i][j]$，并且更新最大星和。

最后返回最大星和即可。

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

func maxStarSum(vals []int, edges [][]int, k int) (ans int) {
	n := len(vals)
	g := make([][]int, n)
	for _, e := range edges {
		a, b := e[0], e[1]
		if vals[b] > 0 {
			g[a] = append(g[a], vals[b])
		}
		if vals[a] > 0 {
			g[b] = append(g[b], vals[a])
		}
	}
	for _, e := range g {
		sort.Sort(sort.Reverse(sort.IntSlice(e)))
	}
	ans = math.MinInt32
	for i, v := range vals {
		for j := 0; j < min(len(g[i]), k); j++ {
			v += g[i][j]
		}
		ans = max(ans, v)
	}
	return
}

力扣原题 · Doocs 题解来源

2508. 添加边使所有节点度数都为偶数

困难1 种解法

标签：图、哈希表

题目、示例与约束

给你一个有 n 个节点的 无向 图，节点编号为 1 到 n 。再给你整数 n 和一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条边。图不一定连通。

你可以给图中添加 至多 两条额外的边（也可以一条边都不添加），使得图中没有重边也没有自环。

如果添加额外的边后，可以使得图中所有点的度数都是偶数，返回 true ，否则返回 false 。

点的度数是连接一个点的边的数目。

 

示例 1：

输入：n = 5, edges = [[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]
输出：true
解释：上图展示了添加一条边的合法方案。
最终图中每个节点都连接偶数条边。

示例 2：

输入：n = 4, edges = [[1,2],[3,4]]
输出：true
解释：上图展示了添加两条边的合法方案。

示例 3：

输入：n = 4, edges = [[1,2],[1,3],[1,4]]
输出：false
解释：无法添加至多 2 条边得到一个符合要求的图。

 

提示：

• 3 <= n <= 105
• 2 <= edges.length <= 105
• edges[i].length == 2
• 1 <= ai, bi <= n
• ai != bi
• 图中不会有重边

方法一：分类讨论 · Go 实现

思考

至多加两条边且不能与已有边重复，要使全部度数变为偶数。握手引理表明奇数度顶点个数必为偶数；加一条边至多改变两个顶点的奇偶，故奇数度顶点超过 $4$ 个时不可能。

用邻接集合建图后取出奇数度顶点 $vs$。 $|vs|=0$ 已满足； $|vs|=2$ 时优先直接连这两点，若已相邻则找一个与二者都未相连的第三点同时连出； $|vs|=4$ 时枚举三种配对方式，存在一对互不相邻的匹配即可。

我们先通过 edges 构建图 $g$，然后找出所有度数为奇数的点，记为 $vs$。

如果 $vs$ 的长度为 $0$，说明图 $g$ 中所有点的度数都是偶数，直接返回 true 即可。

如果 $vs$ 的长度为 $2$，说明图 $g$ 中有两个点的度数是奇数。如果我们可以直接用一条边连接这两个点，使得图 $g$ 中所有点的度数都是偶数，返回 true；否则，如果我们能找到第三个点 $c$，使得我们能够连接 $a$ 和 $c$，以及连接 $b$ 和 $c$，使得图 $g$ 中所有点的度数都是偶数，返回 true；否则，返回 false。

如果 $vs$ 的长度为 $4$，我们枚举两两组合的所有情况，判断是否存在满足条件的情况，是则返回 true；否则，返回 false。

其它情况，返回 false。

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

func isPossible(n int, edges [][]int) bool {
	g := make([]map[int]bool, n+1)
	for _, e := range edges {
		a, b := e[0], e[1]
		if g[a] == nil {
			g[a] = map[int]bool{}
		}
		if g[b] == nil {
			g[b] = map[int]bool{}
		}
		g[a][b], g[b][a] = true, true
	}
	vs := []int{}
	for i := 1; i <= n; i++ {
		if len(g[i])%2 == 1 {
			vs = append(vs, i)
		}
	}
	if len(vs) == 0 {
		return true
	}
	if len(vs) == 2 {
		a, b := vs[0], vs[1]
		if !g[a][b] {
			return true
		}
		for c := 1; c <= n; c++ {
			if a != c && b != c && !g[a][c] && !g[c][b] {
				return true
			}
		}
		return false
	}
	if len(vs) == 4 {
		a, b, c, d := vs[0], vs[1], vs[2], vs[3]
		if !g[a][b] && !g[c][d] {
			return true
		}
		if !g[a][c] && !g[b][d] {
			return true
		}
		if !g[a][d] && !g[b][c] {
			return true
		}
		return false
	}
	return false
}

力扣原题 · Doocs 题解来源

2577. 在网格图中访问一个格子的最少时间

困难1 种解法

标签：广度优先搜索、图、数组、矩阵、最短路、堆（优先队列）

题目、示例与约束

给你一个 m x n 的矩阵 grid ，每个元素都为 非负 整数，其中 grid[row][col] 表示可以访问格子 (row, col) 的 最早 时间。也就是说当你访问格子 (row, col) 时，最少已经经过的时间为 grid[row][col] 。

你从 最左上角 出发，出发时刻为 0 ，你必须一直移动到上下左右相邻四个格子中的 任意 一个格子（即不能停留在格子上）。每次移动都需要花费 1 单位时间。

请你返回 最早 到达右下角格子的时间，如果你无法到达右下角的格子，请你返回 -1 。

 

示例 1：

输入：grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
输出：7
解释：一条可行的路径为：
- 时刻 t = 0 ，我们在格子 (0,0) 。
- 时刻 t = 1 ，我们移动到格子 (0,1) ，可以移动的原因是 grid[0][1] <= 1 。
- 时刻 t = 2 ，我们移动到格子 (1,1) ，可以移动的原因是 grid[1][1] <= 2 。
- 时刻 t = 3 ，我们移动到格子 (1,2) ，可以移动的原因是 grid[1][2] <= 3 。
- 时刻 t = 4 ，我们移动到格子 (1,1) ，可以移动的原因是 grid[1][1] <= 4 。
- 时刻 t = 5 ，我们移动到格子 (1,2) ，可以移动的原因是 grid[1][2] <= 5 。
- 时刻 t = 6 ，我们移动到格子 (1,3) ，可以移动的原因是 grid[1][3] <= 6 。
- 时刻 t = 7 ，我们移动到格子 (2,3) ，可以移动的原因是 grid[2][3] <= 7 。
最终到达时刻为 7 。这是最早可以到达的时间。

示例 2：

输入：grid = [[0,2,4],[3,2,1],[1,0,4]]
输出：-1
解释：没法从左上角按题目规定走到右下角。

 

提示：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 105
• 0 <= grid[i][j] <= 105
• grid[0][0] == 0

方法一：最短路 + 优先队列（小根堆） · Go 实现

思考

进入格子的时刻必须不小于其上数字，每步耗时 $1$，可在已访问格子间来回等待。起点的两邻若都大于 $1$，则第一步都走不出去。

其余情形总能靠来回把奇偶调整到合法到达时刻。这是带等待的最短路：小根堆按到达时间扩展。若 $t+1$ 已不小于格子值则下一步即 $t+1$；否则等到 $grid[x][y]$，并在与 $t+1$ 奇偶不同时再多等一秒。

我们观察发现，如果在格子 $(0,0)$ 处无法移动，即 $grid[0][1]>1$ 且 $grid[1][0]>1$，那么我们在格子 $(0,0)$ 无法再移动，此时返回 $-1$ 即可。而对于其他情况，我们都可以移动。

接下来，我们定义 $dist[i][j]$ 表示 $(i,j)$ 处的最早到达时间，初始时 $dist[0][0]=0$，而其他位置的 $dist$ 均初始化为 $\mathrm{\infty }$。

我们使用优先队列（小根堆）来维护当前可以移动的格子，优先队列中的元素为 $(dist[i][j],i,j)$，即 $(dist[i][j],i,j)$ 表示 $(i,j)$ 处的最早到达时间。

我们每次从优先队列中取出当前最早到达的格子 $(t,i,j)$，如果 $(i,j)$ 为 $(m-1,n-1)$，那么我们直接返回 $t$ 即可，否则，我们遍历 $(i,j)$ 的上下左右四个相邻格子 $(x,y)$，如果 $t+1<grid[x][y]$，那么我们移动到 $(x,y)$ 的时间 $nt=grid[x][y]+(grid[x][y]-(t+1))mod2$，此时我们可以通过反复移动将时间拉长至不小于 $grid[x][y]$，这取决于 $t+1$ 和 $grid[x][y]$ 距离的奇偶性。否则，我们移动到 $(x,y)$ 的时间 $nt=t+1$。如果 $nt<dist[x][y]$，那么我们更新 $dist[x][y]=nt$，并将 $(nt,x,y)$ 加入优先队列中。

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

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

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 题解来源

2603. 收集树中金币

困难1 种解法

标签：树、图、拓扑排序、数组

题目、示例与约束

给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。

一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：

• 收集距离当前节点距离为 2 以内的所有金币，或者
• 移动到树中一个相邻节点。

你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。

如果你多次经过一条边，每一次经过都会给答案加一。

 

示例 1：

输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：从节点 2 出发，收集节点 0 处的金币，移动到节点 3 ，收集节点 5 处的金币，然后移动回节点 2 。

示例 2：

输入：coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
输出：2
解释：从节点 0 出发，收集节点 4 和 3 处的金币，移动到节点 2 处，收集节点 7 处的金币，移动回节点 0 。

 

提示：

• n == coins.length
• 1 <= n <= 3 * 104
• 0 <= coins[i] <= 1
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• edges 表示一棵合法的树。

方法一：拓扑排序 · Go 实现

思考

收集全部金币后须回到起点，每条边至多走两次。若对整棵树做欧拉遍历，会把远离金币的枝条和「站在距金币 $2$ 步处即可收取」的叶子一并计入。 $n\le {10}^5$，需要线性剥层。

无金币的叶子永远不必访问，可反复删去直至剩下的叶子都带金币。题目允许距离 $2$ 内收取，故再剥两层叶子后，剩余连通块才是必须往返的骨架。

用队列做拓扑式删叶：先清掉无金币叶子，再删两轮当前叶子，最后统计仍两端都在骨架上的边数并乘 $2$。

我们先将 $edges$ 中的边转换成邻接表 $g$，其中 $g[i]$ 表示节点 $i$ 的所有邻接节点，用集合表示。

接下来我们遍历所有节点，找到 $coins[i]=0$ 且 $g[i]$ 中只有一个节点的节点（也即是金币为 $0$ 的叶子节点），将其加入队列 $q$ 中。

然后我们不断地从队列中取出节点，将其从邻接表中删除，然后判断其邻接节点是否满足 $coins[j]=0$ 且 $g[j]$ 中只有一个节点的条件，如果满足则将其加入队列 $q$ 中。循环，直至队列为空。

经过上述操作后，我们得到了一棵新的树，且树的叶子节点都是金币为 $1$ 的节点。

然后，我们再删除剩下的两层叶子节点，最终得到的是一棵所有节点都需要被访问的节点，我们只需要统计其边数，乘上 $2$，即为答案。

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

相似题目：

• 2204. 无向图中到环的距离

func collectTheCoins(coins []int, edges [][]int) int {
	n := len(coins)
	g := make([]map[int]bool, n)
	for i := range g {
		g[i] = map[int]bool{}
	}
	for _, e := range edges {
		a, b := e[0], e[1]
		g[a][b] = true
		g[b][a] = true
	}
	q := []int{}
	for i, c := range coins {
		if c == 0 && len(g[i]) == 1 {
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		i := q[0]
		q = q[1:]
		for j := range g[i] {
			delete(g[j], i)
			if coins[j] == 0 && len(g[j]) == 1 {
				q = append(q, j)
			}
		}
		g[i] = map[int]bool{}
	}
	for k := 0; k < 2; k++ {
		q := []int{}
		for i := range coins {
			if len(g[i]) == 1 {
				q = append(q, i)
			}
		}
		for _, i := range q {
			for j := range g[i] {
				delete(g[j], i)
			}
			g[i] = map[int]bool{}
		}
	}
	ans := 0
	for _, e := range edges {
		a, b := e[0], e[1]
		if len(g[a]) > 0 && len(g[b]) > 0 {
			ans += 2
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2608. 图中的最短环

困难2 种解法

标签：广度优先搜索、图

题目、示例与约束

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

返回图中 最短 环的长度。如果不存在环，则返回 -1 。

环 是指以同一节点开始和结束，并且路径中的每条边仅使用一次。

 

示例 1：

输入：n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
输出：3
解释：长度最小的循环是：0 -> 1 -> 2 -> 0 

示例 2：

输入：n = 4, edges = [[0,1],[0,2]]
输出：-1
解释：图中不存在循环

 

提示：

• 2 <= n <= 1000
• 1 <= edges.length <= 1000
• edges[i].length == 2
• 0 <= ui, vi < n
• ui != vi
• 不存在重复的边

方法一：枚举删除的边 + BFS · Go 实现

思考

无向图最短环可对每条边「删边后求两端最短路」。 $n\le 1000$、 $m\le 1000$，每次 BFS 为 $O(n+m)$，总时间 $O(m(n+m))$ 可接受。

环必然包含某条边 $(u,v)$，删去它后 $u$ 到 $v$ 的最短路长度加 $1$ 即含该边的最短环。对全部边取最小；若均不连通则无环。

我们先根据数组 $edges$ 构建出邻接表 $g$，其中 $g[u]$ 表示顶点 $u$ 的所有邻接点。

接下来，我们枚举双向边 $(u,v)$，如果删除该边后，从顶点 $u$ 到顶点 $v$ 的路径依然存在，则包含该边的最短环的长度为 $dist[v]+1$，其中 $dist[v]$ 表示从顶点 $u$ 到顶点 $v$ 的最短路径长度。我们取所有这样的环的最小值即可。

时间复杂度 $O(m^2)$，空间复杂度 $O(m+n)$。其中 $m$ 和 $n$ 分别为数组 $edges$ 的长度以及顶点数。

func findShortestCycle(n int, edges [][]int) int {
	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)
	}
	const inf = 1 << 30
	bfs := func(u, v int) int {
		dist := make([]int, n)
		for i := range dist {
			dist[i] = inf
		}
		dist[u] = 0
		q := []int{u}
		for len(q) > 0 {
			i := q[0]
			q = q[1:]
			for _, j := range g[i] {
				if (i == u && j == v) || (i == v && j == u) || dist[j] != inf {
					continue
				}
				dist[j] = dist[i] + 1
				q = append(q, j)
			}
		}
		return dist[v] + 1
	}
	ans := inf
	for _, e := range edges {
		u, v := e[0], e[1]
		ans = min(ans, bfs(u, v))
	}
	if ans < inf {
		return ans
	}
	return -1
}

方法二：枚举点 + BFS · Go 实现

思考

方法一对每条边各做一次 BFS。改为以每个顶点为源做一次 BFS：首次遇到非父节点的已访问邻居，即闭合一条环，长度为两边距离之和加 $1$。

边数较大时源点次数更少，复杂度变为 $O(n(n+m))$，实现上无需反复删边。

与方法一类似，我们先根据数组 $edges$ 构建出邻接表 $g$，其中 $g[u]$ 表示顶点 $u$ 的所有邻接点。

接下来，我们枚举顶点 $u$，如果从顶点 $u$ 出发，有两条路径都到达了顶点 $v$，说明当前找到了一个环，长度为两条路径的长度之和。我们取所有这样的环的最小值即可。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m+n)$。其中 $m$ 和 $n$ 分别为数组 $edges$ 的长度以及顶点数。

func findShortestCycle(n int, edges [][]int) int {
	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)
	}
	const inf = 1 << 30
	bfs := func(u int) int {
		dist := make([]int, n)
		for i := range dist {
			dist[i] = -1
		}
		dist[u] = 0
		q := [][2]int{{u, -1}}
		ans := inf
		for len(q) > 0 {
			p := q[0]
			u = p[0]
			fa := p[1]
			q = q[1:]
			for _, v := range g[u] {
				if dist[v] < 0 {
					dist[v] = dist[u] + 1
					q = append(q, [2]int{v, u})
				} else if v != fa {
					ans = min(ans, dist[u]+dist[v]+1)
				}
			}
		}
		return ans
	}
	ans := inf
	for i := 0; i < n; i++ {
		ans = min(ans, bfs(i))
	}
	if ans < inf {
		return ans
	}
	return -1
}

力扣原题 · Doocs 题解来源