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

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

来源与许可

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

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

133. 克隆图

中等1 种解法

标签：深度优先搜索、广度优先搜索、图、哈希表

题目、示例与约束

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

class Node {
    public int val;
    public List<Node> neighbors;
}

 

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

 

示例 1：

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

示例 2：

输入：adjList = [[]]
输出：[[]]
解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。

示例 3：

输入：adjList = []
输出：[]
解释：这个图是空的，它不含任何节点。

 

提示：

• 这张图中的节点数在 [0, 100] 之间。
• 1 <= Node.val <= 100
• 每个节点值 Node.val 都是唯一的，
• 图中没有重复的边，也没有自环。
• 图是连通图，你可以从给定节点访问到所有节点。

方法一：哈希表 + DFS · Go 实现

思考

深拷贝连通无向图，节点值唯一， $n\le 100$。只复制值不够，邻居指针必须指向新图中的对应节点，且图中有环，直接递归会转圈。

用哈希表记下「原节点 → 副本」。第一次访问时建好副本再递归邻居，再次遇到同一节点则直接返回已有副本，环被截断。

我们用一个哈希表 $\mathit{\text{g}}$ 记录原图中的每个节点和它的拷贝节点之间的对应关系，然后进行深度优先搜索。

我们定义函数 $\text{dfs}(node)$，它的功能是返回 $\mathit{\text{node}}$ 节点的拷贝节点。 $\text{dfs}(node)$ 的过程如下：

• 如果 $\mathit{\text{node}}$ 是 $\text{null}$，那么 $\text{dfs}(node)$ 的返回值是 $\text{null}$。
• 如果 $\mathit{\text{node}}$ 在 $\mathit{\text{g}}$ 中，那么 $\text{dfs}(node)$ 的返回值是 $\mathit{\text{g}}[node]$。
• 否则我们创建一个新的节点 $\mathit{\text{cloned}}$，并将 $\mathit{\text{g}}[node]$ 的值设为 $\mathit{\text{cloned}}$，然后遍历 $\mathit{\text{node}}$ 的所有邻居节点 $\mathit{\text{nxt}}$，并将 $\mathit{\text{cloned}}$ 的邻居节点列表中加入 $\text{dfs}(nxt)$。
• 最后返回 $\mathit{\text{cloned}}$。

在主函数中，我们返回 $\text{dfs}(node)$。

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

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Neighbors []*Node
 * }
 */

func cloneGraph(node *Node) *Node {
	g := map[*Node]*Node{}
	var dfs func(node *Node) *Node
	dfs = func(node *Node) *Node {
		if node == nil {
			return nil
		}
		if n, ok := g[node]; ok {
			return n
		}
		cloned := &Node{node.Val, []*Node{}}
		g[node] = cloned
		for _, nxt := range node.Neighbors {
			cloned.Neighbors = append(cloned.Neighbors, dfs(nxt))
		}
		return cloned
	}
	return dfs(node)
}

力扣原题 · Doocs 题解来源

207. 课程表

中等1 种解法

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

题目、示例与约束

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

 

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

 

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同

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

思考

先修关系构成有向图，能修完所有课当且仅当图中无环。枚举排列检查约束在课程数较大时不可行。

拓扑排序不断取出入度为 $0$ 的课并减少其后继入度；若全部结点都能入队则无环，否则存在环。

对于本题，我们可以将课程看作图中的节点，先修课程看作图中的边，那么我们可以将本题转化为判断有向图中是否存在环。

具体地，我们可以使用拓扑排序的思想，对于每个入度为 $0$ 的节点，我们将其出度的节点的入度减 $1$，直到所有节点都被遍历到。

如果所有节点都被遍历到，说明图中不存在环，那么我们就可以完成所有课程的学习；否则，我们就无法完成所有课程的学习。

时间复杂度 $O(n+m)$，空间复杂度 $O(n+m)$。其中 $n$ 和 $m$ 分别为课程数和先修课程数。

func canFinish(numCourses int, prerequisites [][]int) bool {
	g := make([][]int, numCourses)
	indeg := make([]int, numCourses)
	for _, p := range prerequisites {
		a, b := p[0], p[1]
		g[b] = append(g[b], a)
		indeg[a]++
	}
	q := []int{}
	for i, x := range indeg {
		if x == 0 {
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		i := q[0]
		q = q[1:]
		numCourses--
		for _, j := range g[i] {
			indeg[j]--
			if indeg[j] == 0 {
				q = append(q, j)
			}
		}
	}
	return numCourses == 0
}

力扣原题 · Doocs 题解来源

210. 课程表 II

中等1 种解法

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

题目、示例与约束

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

• 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

 

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]

 

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• 所有[ai, bi] 互不相同

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

思考

与“能否修完”相同，先修关系给出有向图，还需要一种合法顺序。拓扑排序的出队次序即为一种修课序列。

若入队课程数不足 $numCourses$，则存在环，返回空数组。

我们创建一个邻接表 $g$，用于存储每个节点的后继节点，同时还需要一个数组 $indeg$ 存储每个节点的入度。在构建邻接表的同时，我们也统计每个节点的入度。当入度为 $0$ 的节点代表没有任何前置课程，可以直接学习，我们将其加入队列 $q$ 中。

当队列 $q$ 不为空的时候，我们取出队首的节点 $i$：

• 我们将 $i$ 放入答案中；
• 接下来，我们将 $i$ 的所有后继节点的入度减少 $1$。如果发现某个后继节点 $j$ 的入度变为 $0$，则将 $j$ 放入队列 $q$ 中。

在广度优先搜索的结束时，如果答案中包含了这 $n$ 个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。

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

func findOrder(numCourses int, prerequisites [][]int) []int {
	g := make([][]int, numCourses)
	indeg := make([]int, numCourses)
	for _, p := range prerequisites {
		a, b := p[0], p[1]
		g[b] = append(g[b], a)
		indeg[a]++
	}
	q := []int{}
	for i, x := range indeg {
		if x == 0 {
			q = append(q, i)
		}
	}
	ans := []int{}
	for len(q) > 0 {
		i := q[0]
		q = q[1:]
		ans = append(ans, i)
		for _, j := range g[i] {
			indeg[j]--
			if indeg[j] == 0 {
				q = append(q, j)
			}
		}
	}
	if len(ans) == numCourses {
		return ans
	}
	return []int{}
}

力扣原题 · Doocs 题解来源

269. 火星词典 🔒

困难1 种解法

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

题目、示例与约束

现有一种使用英语字母的火星语言，这门语言的字母顺序对你来说是未知的。

给你一个来自这种外星语言字典的字符串列表 words ，words 中的字符串已经 按这门新语言的字典序进行了排序 。

如果这种说法是错误的，并且给出的 words 不能对应任何字母的顺序，则返回 "" 。

否则，返回一个按新语言规则的 字典递增顺序 排序的独特字符串。如果有多个解决方案，则返回其中 任意一个 。

 

示例 1：

输入：words = ["wrt","wrf","er","ett","rftt"]
输出："wertf"

示例 2：

输入：words = ["z","x"]
输出："zx"

示例 3：

输入：words = ["z","x","z"]
输出：""
解释：不存在合法字母顺序，因此返回 "" 。

 

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] 仅由小写英文字母组成

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

思考

字典序由相邻单词的第一处不同字母给出有向边。后一词是前一词前缀、或出现反向边，则无合法序。

对出现过的字母做拓扑排序：入度为 $0$ 的入队，排出顺序即为字母序；排出个数不足则有环。

用数组 $g$ 记录在火星字典中的字母先后关系， $g[i][j]=true$ 表示字母 $i{+}^{\prime }{a}^{\prime }$ 在字母 $j{+}^{\prime }{a}^{\prime }$ 的前面；用数组 $s$ 记录当前字典出现过的字母， $cnt$ 表示出现过的字母数。

一个很简单的想法是遍历每一个单词，比较该单词和其后的所有单词，把所有的先后关系更新进数组 $g$，这样遍历时间复杂度为 $O(n^3)$；但是我们发现其实比较相邻的两个单词就可以了，比如 $a<b<c$ 则比较 $a<b$ 和 $b<c$， $a$ 和 $c$ 的关系便确定了。因此算法可以优化成比较相邻两个单词，时间复杂度为 $O(n²)$。

出现矛盾的情况：

• $g[i][j]$ = $g[j][i]$ = $true$；
• 后一个单词是前一个单词的前缀；
• 在拓扑排序后 $ans$ 的长度小于统计到的字母个数。

拓扑排序：

• 统计所有出现的字母入度；
• 将所有入度为 $0$ 的字母加入队列；
• 当队列不空，出队并更新其他字母的入度，入度为 $0$ 则入队，同时出队时将当前字母加入 $ans$ 的结尾；
• 得到的便是字母的拓扑序，也就是火星字典的字母顺序。

func alienOrder(words []string) string {
	g := [26][26]bool{}
	s := [26]bool{}
	cnt := 0
	n := len(words)
	for i := 0; i < n-1; i++ {
		for _, c := range words[i] {
			if cnt == 26 {
				break
			}
			c -= 'a'
			if !s[c] {
				cnt++
				s[c] = true
			}
		}
		m := len(words[i])
		for j := 0; j < m; j++ {
			if j >= len(words[i+1]) {
				return ""
			}
			c1, c2 := words[i][j]-'a', words[i+1][j]-'a'
			if c1 == c2 {
				continue
			}
			if g[c2][c1] {
				return ""
			}
			g[c1][c2] = true
			break
		}
	}
	for _, c := range words[n-1] {
		if cnt == 26 {
			break
		}
		c -= 'a'
		if !s[c] {
			cnt++
			s[c] = true
		}
	}

	inDegree := [26]int{}
	for _, out := range g {
		for i, v := range out {
			if v {
				inDegree[i]++
			}
		}
	}
	q := []int{}
	for i, in := range inDegree {
		if in == 0 && s[i] {
			q = append(q, i)
		}
	}
	ans := ""
	for len(q) > 0 {
		t := q[0]
		q = q[1:]
		ans += string(t + 'a')
		for i, v := range g[t] {
			if v {
				inDegree[i]--
				if inDegree[i] == 0 && s[i] {
					q = append(q, i)
				}
			}
		}
	}
	if len(ans) < cnt {
		return ""
	}
	return ans
}

力扣原题 · Doocs 题解来源

277. 搜寻名人 🔒

中等1 种解法

标签：图、双指针、交互

题目、示例与约束

假设你是一个专业的狗仔，参加了一个 n 人派对，其中每个人被从 0 到 n - 1 标号。在这个派对人群当中可能存在一位 “名人”。所谓 “名人” 的定义是：其他所有 n - 1 个人都认识他/她，而他/她并不认识其他任何人。

现在你想要确认这个 “名人” 是谁，或者确定这里没有 “名人”。而你唯一能做的就是问诸如 “A 你好呀，请问你认不认识 B呀？” 的问题，以确定 A 是否认识 B。你需要在（渐近意义上）尽可能少的问题内来确定这位 “名人” 是谁（或者确定这里没有 “名人”）。

给定整数 n 和一个辅助函数 bool knows(a, b) 用来获取 a 是否认识 b。实现一个函数 int findCelebrity(n)。派对最多只会有一个 “名人” 参加。

若 “名人” 存在，请返回他/她的编号；若 “名人” 不存在，请返回 -1。

注意 n x n 的二维数组 graph 给定的输入并不是 直接 提供给你的，而是 只能 通过辅助函数 knows 获取。graph[i][j] == 1 表示 i 认识 j，而 graph[i][j] == 0 表示 j 不认识 i。

 

示例 1:

输入: graph = [[1,1,0],[0,1,0],[1,1,1]]
输出: 1
解释: 有编号分别为 0、1 和 2 的三个人。graph[i][j] = 1 代表编号为 i 的人认识编号为 j 的人，而 graph[i][j] = 0 则代表编号为 i 的人不认识编号为 j 的人。“名人” 是编号 1 的人，因为 0 和 2 均认识他/她，但 1 不认识任何人。

示例 2:

输入: graph = [[1,0,1],[1,1,0],[0,1,1]]
输出: -1
解释: 没有 “名人”

 

提示：

• n == graph.length == graph[i].length
• 2 <= n <= 100
• graph[i][j] 是 0 或 1
• graph[i][i] == 1

 

进阶：如果允许调用 API knows 的最大次数为 3 * n ，你可以设计一个不超过最大调用次数的解决方案吗？

方法一：O(n) 遍历 · Go 实现

思考

对每对人调用 $knows$ 是平方次询问。名人至多一个：若 $a$ 认识 $b$，则 $a$ 不是名人，候选人可换成 $b$。

先线性选出唯一候选，再验证他不认识任何人且所有人都认识他。

经过验证，若暴力遍历，调用 $O(n^2)$ 次 $knows$ 方法，会报 TLE 错误。因此，我们需要寻找更优的解法。

要找出 $n$ 个人中的名人，题目给我们的关键信息是：1. 名人不认识其他所有人；2. 其他所有人都认识名人。

那么，我们初始时假定名人 $ans=0$。然后在 $[1,n)$ 范围内遍历 $i$，若 $ans$ 认识 $i$，说明 $ans$ 不是我们要找的名人，此时我们可以直接将 $ans$ 更新为 $i$。

为什么呢？我们来举个实际的例子。

ans = 0
for i in [1,n) {
	if (ans knows i) {
		ans = i
	}
}

ans = 0

ans not knows 1
ans not knows 2
ans knows 3
ans = 3

ans not knows 4
ans not knows 5
ans not knows 6
ans = 6

这里 $ans$ 认识 $3$，说明 $ans$ 不是名人（即 $0$ 不是名人），那么名人会是 $1$ 或者 $2$ 吗？不会！因为若 $1$ 或者 $2$ 是名人，那么 $0$ 应该认识 $1$ 或者 $2$ 才对，与前面的例子冲突。因此，我们可以直接将 $ans$ 更新为 $i$。

我们找出 $ans$ 之后，接下来再遍历一遍，判断 $ans$ 是否满足名人的条件。若不满足，返回 $-1$。

否则遍历结束，返回 $ans$。

/**
 * The knows API is already defined for you.
 *     knows := func(a int, b int) bool
 */
func solution(knows func(a int, b int) bool) func(n int) int {
	return func(n int) int {
		ans := 0
		for i := 1; i < n; i++ {
			if knows(ans, i) {
				ans = i
			}
		}
		for i := 0; i < n; i++ {
			if ans != i {
				if knows(ans, i) || !knows(i, ans) {
					return -1
				}
			}
		}
		return ans
	}
}

力扣原题 · Doocs 题解来源

310. 最小高度树

中等1 种解法

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

题目、示例与约束

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，任何一个没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

 

示例 1：

输入：n = 4, edges = [[1,0],[1,2],[1,3]]
输出：[1]
解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。

示例 2：

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

 

提示：

• 1 <= n <= 2 * 104
• edges.length == n - 1
• 0 <= ai, bi < n
• ai != bi
• 所有 (ai, bi) 互不相同
• 给定的输入 保证 是一棵树，并且 不会有重复的边

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

思考

高度是根到最远叶的距离。若对每个点当根做一次 BFS，总代价为 $O(n^2)$。树的直径中心至多两个，它们恰为最小高度的根。

叶子度数为 $1$。从全部叶子同时向内剥层，相当于拓扑排序：每剥一层，邻点度数减一，新叶子入队。最后一层剩下的 $1$ 或 $2$ 个结点即中心。单结点特判直接返回。

如果这棵树只有一个节点，那么这个节点就是最小高度树的根节点，直接返回这个节点即可。

如果这棵树有多个节点，那么一定存在叶子节点。叶子节点是只有一个相邻节点的节点。我们可以利用拓扑排序，从外向内剥离叶子节点，当我们到达最后一层的时候，剩下的节点就是最小高度树的根节点。

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

func findMinHeightTrees(n int, edges [][]int) (ans []int) {
	if n == 1 {
		return []int{0}
	}
	g := make([][]int, n)
	degree := 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)
		degree[a]++
		degree[b]++
	}
	q := []int{}
	for i, d := range degree {
		if d == 1 {
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		ans = []int{}
		for i := len(q); i > 0; i-- {
			a := q[0]
			q = q[1:]
			ans = append(ans, a)
			for _, b := range g[a] {
				degree[b]--
				if degree[b] == 1 {
					q = append(q, b)
				}
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

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

困难1 种解法

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

题目、示例与约束

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

 

示例 1：

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4 
解释：最长递增路径为 [1, 2, 6, 9]。

示例 2：

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4 
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例 3：

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

 

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 231 - 1

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

思考

四向严格递增路径的最长长度。朴素 DFS 会在同一格子重复出发。路径无环（值严格增大），子问题无后效。

$dfs(i,j)$ 取四邻中更大格子的最长路径再加一。记忆化后每个格子只算一次，答案为所有起点的最大值。

我们设计一个函数 $dfs(i,j)$，它表示从矩阵中的坐标 $(i,j)$ 出发，可以得到的最长递增路径的长度。那么答案就是 $\underset{i,j}{max}\mathit{\text{dfs}}(i,j)$。

函数 $dfs(i,j)$ 的执行逻辑如下：

• 如果 $(i,j)$ 已经被访问过，直接返回 $\mathit{\text{f}}(i,j)$；
• 否则对 $(i,j)$ 进行搜索，搜索四个方向的坐标 $(x,y)$，如果满足 $0\le x<m,0\le y<n$ 以及 $matrix[x][y]>matrix[i][j]$，那么对 $(x,y)$ 进行搜索。搜索结束后，将 $\mathit{\text{f}}(i,j)$ 更新为 $\mathit{\text{f}}(i,j)=max(\mathit{\text{f}}(i,j),\mathit{\text{f}}(x,y)+1)$。最后返回 $\mathit{\text{f}}(i,j)$。

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

相似题目：

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

func longestIncreasingPath(matrix [][]int) (ans int) {
	m, n := len(matrix), len(matrix[0])
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
	}
	dirs := [5]int{-1, 0, 1, 0, -1}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if f[i][j] != 0 {
			return f[i][j]
		}
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if 0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j] {
				f[i][j] = max(f[i][j], dfs(x, y))
			}
		}
		f[i][j]++
		return f[i][j]
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			ans = max(ans, dfs(i, j))
		}
	}
	return
}

力扣原题 · Doocs 题解来源

332. 重新安排行程

困难1 种解法

标签：深度优先搜索、图、数组、字符串、排序、欧拉路径、欧拉回路、堆（优先队列）、半欧拉图

题目、示例与约束

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

• 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

 

示例 1：

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2：

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

 

提示：

• 1 <= tickets.length <= 300
• tickets[i].length == 2
• fromi.length == 3
• toi.length == 3
• fromi 和 toi 由大写英文字母组成
• fromi != toi

方法一：欧拉路径 · Go 实现

思考

每张机票用且仅用一次，行程字典序最小。这是有向图的欧拉路径，Hierholzer 从 JFK 出发即可。

先按终点逆序存边，弹出时即得字典序最小的下一条。后序把结点写入答案再反转，保证死胡同先记下、主干后走。题目保证有解。

题目实际上是给定 $n$ 个点和 $m$ 条边，要求从指定的起点出发，经过所有的边恰好一次，使得路径字典序最小。这是一个典型的欧拉路径问题。

由于本题保证了至少存在一种合理的行程，因此，我们直接利用 Hierholzer 算法，输出从起点出发的欧拉路径即可。

时间复杂度 $O(m\times \log m)$，空间复杂度 $O(m)$。其中 $m$ 是边的数量。

func findItinerary(tickets [][]string) (ans []string) {
	sort.Slice(tickets, func(i, j int) bool {
		return tickets[i][0] > tickets[j][0] || (tickets[i][0] == tickets[j][0] && tickets[i][1] > tickets[j][1])
	})
	g := make(map[string][]string)
	for _, ticket := range tickets {
		g[ticket[0]] = append(g[ticket[0]], ticket[1])
	}
	var dfs func(f string)
	dfs = func(f string) {
		for len(g[f]) > 0 {
			t := g[f][len(g[f])-1]
			g[f] = g[f][:len(g[f])-1]
			dfs(t)
		}
		ans = append(ans, f)
	}
	dfs("JFK")
	for i := 0; i < len(ans)/2; i++ {
		ans[i], ans[len(ans)-1-i] = ans[len(ans)-1-i], ans[i]
	}
	return
}

力扣原题 · Doocs 题解来源

444. 序列重建 🔒

中等1 种解法

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

题目、示例与约束

给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。
检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列，并且所有序列 sequences[i] 都是它的子序列。对于给定的数组 sequences ，可能存在多个有效的 超序列 。

• 例如，对于 sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。
• 而对于 sequences = [[1,2],[1,3],[1,2,3]] ，唯一可能的最短 超序列 是 [1,2,3] 。[1,2,3,4] 是可能的超序列，但不是最短的。

如果 nums 是序列的唯一最短 超序列 ，则返回 true ，否则返回 false 。
子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。

 

示例 1：

输入：nums = [1,2,3], sequences = [[1,2],[1,3]]
输出：false
解释：有两种可能的超序列：[1,2,3]和[1,3,2]。
序列 [1,2] 是[1,2,3]和[1,3,2]的子序列。
序列 [1,3] 是[1,2,3]和[1,3,2]的子序列。
因为 nums 不是唯一最短的超序列，所以返回false。

示例 2：

输入：nums = [1,2,3], sequences = [[1,2]]
输出：false
解释：最短可能的超序列为 [1,2]。
序列 [1,2] 是它的子序列：[1,2]。
因为 nums 不是最短的超序列，所以返回false。

示例 3：

输入：nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
输出：true
解释：最短可能的超序列为[1,2,3]。
序列 [1,2] 是它的一个子序列：[1,2,3]。
序列 [1,3] 是它的一个子序列：[1,2,3]。
序列 [2,3] 是它的一个子序列：[1,2,3]。
因为 nums 是唯一最短的超序列，所以返回true。

 

提示：

• n == nums.length
• 1 <= n <= 104
• nums 是 [1, n] 范围内所有整数的排列
• 1 <= sequences.length <= 104
• 1 <= sequences[i].length <= 104
• 1 <= sum(sequences[i].length) <= 105
• 1 <= sequences[i][j] <= n
• sequences 的所有数组都是 唯一 的
• sequences[i] 是 nums 的一个子序列

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

思考

要判断 $nums$ 是否为所有序列的唯一最短超序列。多个拓扑序意味着超序列不唯一。

把每个 $\mathit{\text{seq}}$ 的相邻对建成有向边并统计入度。队列里始终只能有一个入度为 $0$ 的点，才能逐步确定唯一顺序；一旦同时出现两个，返回失败。

循环结束时队列为空则全部排出，顺序唯一。不必与 $nums$ 逐位比较：唯一拓扑序若存在，只能是 $nums$（题目保证 $nums$ 是 $[1,n]$ 的排列且覆盖）。

我们可以先遍历每个子序列 seq，对于每个相邻的元素 $a$ 和 $b$，我们在 $a$ 和 $b$ 之间建立一条有向边 $a\to b$。同时统计每个节点的入度，最后将所有入度为 $0$ 的节点加入队列中。

当队列中的节点个数等于 $1$ 时，我们取出队首节点 $i$，将 $i$ 从图中删除，并将 $i$ 的所有相邻节点的入度减 $1$。如果减 $1$ 后相邻节点的入度为 $0$，则将这些节点加入队列中。重复上述操作，直到队列的长度不为 $1$。此时判断队列是否为空，如果不为空，说明有多个最短超序列，返回 false；如果为空，说明只有一个最短超序列，返回 true。

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

func sequenceReconstruction(nums []int, sequences [][]int) bool {
	n := len(nums)
	indeg := make([]int, n)
	g := make([][]int, n)
	for _, seq := range sequences {
		for i, b := range seq[1:] {
			a := seq[i] - 1
			b -= 1
			g[a] = append(g[a], b)
			indeg[b]++
		}
	}
	q := []int{}
	for i, x := range indeg {
		if x == 0 {
			q = append(q, i)
		}
	}
	for len(q) == 1 {
		i := q[0]
		q = q[1:]
		for _, j := range g[i] {
			indeg[j]--
			if indeg[j] == 0 {
				q = append(q, j)
			}
		}
	}
	return len(q) == 0
}

力扣原题 · Doocs 题解来源

499. 迷宫 III 🔒

困难1 种解法

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

题目、示例与约束

由空地和墙组成的迷宫中有一个球。球可以向上（u）下（d）左（l）右（r）四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向（必须与上一个选择的方向不同）。迷宫中还有一个洞，当球运动经过洞时，就会掉进洞里。

给定球的起始位置，目的地和迷宫，找出让球以最短距离掉进洞里的路径。 距离的定义是球从起始位置（不包括）到目的地（包括）经过的空地个数。通过'u', 'd', 'l' 和 'r'输出球的移动方向。 由于可能有多条最短路径， 请输出字典序最小的路径。如果球无法进入洞，输出"impossible"。

迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。

 

示例1:

输入 1: 迷宫由以下二维数组表示

0 0 0 0 0
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 1 0 0 0

输入 2: 球的初始位置 (rowBall, colBall) = (4, 3)
输入 3: 洞的位置 (rowHole, colHole) = (0, 1)

输出: "lul"

解析: 有两条让球进洞的最短路径。
第一条路径是 左 -> 上 -> 左, 记为 "lul".
第二条路径是 上 -> 左, 记为 'ul'.
两条路径都具有最短距离6, 但'l' < 'u'，故第一条路径字典序更小。因此输出"lul"。

示例 2:

输入 1: 迷宫由以下二维数组表示

0 0 0 0 0
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 1 0 0 0

输入 2: 球的初始位置 (rowBall, colBall) = (4, 3)
输入 3: 洞的位置 (rowHole, colHole) = (3, 0)

输出: "impossible"

示例: 球无法到达洞。

示例 3：

输入：maze = [[0,0,0,0,0,0,0],[0,0,1,0,0,1,0],[0,0,0,0,1,0,0],[0,0,0,0,0,0,1]], ball = [0,4], hole = [3,5]
输出："dldr"

 

提示：

• m == maze.length
• n == maze[i].length
• 1 <= m, n <= 100
• maze[i][j] is 0 or 1.
• ball.length == 2
• hole.length == 2
• 0 <= ballrow, holerow <= m
• 0 <= ballcol, holecol <= n
• 球和洞都存在于一个空地中，它们最初不会处于同一位置。
• 迷宫中至少有 2 个空地。

方法一：BFS · Go 实现

思考

球滚到墙或洞口才停，求到达洞口的最短路径；距离相同则取字典序最小的方向串。普通 BFS 只比距离，不够。

对每个停点记录最短步数与对应路径。沿四向滚动，遇洞立即停下。若新步数更小，或步数相同但路径更小，则更新并（未入洞时）入队。

洞不是墙，滚动循环必须额外判断是否已到洞。路径字符串随距离一起松弛，才能同时满足最短与字典序。

import "math"

func findShortestWay(maze [][]int, ball []int, hole []int) string {
	m, n := len(maze), len(maze[0])
	r, c := ball[0], ball[1]
	rh, ch := hole[0], hole[1]
	q := [][]int{[]int{r, c}}
	dist := make([][]int, m)
	path := make([][]string, m)
	for i := range dist {
		dist[i] = make([]int, n)
		path[i] = make([]string, n)
		for j := range dist[i] {
			dist[i][j] = math.MaxInt32
			path[i][j] = ""
		}
	}
	dist[r][c] = 0
	dirs := map[string][]int{"u": {-1, 0}, "d": {1, 0}, "l": {0, -1}, "r": {0, 1}}
	for len(q) > 0 {
		p := q[0]
		q = q[1:]
		i, j := p[0], p[1]
		for d, dir := range dirs {
			a, b := dir[0], dir[1]
			x, y := i, j
			step := dist[i][j]
			for x+a >= 0 && x+a < m && y+b >= 0 && y+b < n && maze[x+a][y+b] == 0 && (x != rh || y != ch) {
				x += a
				y += b
				step++
			}
			if dist[x][y] > step || (dist[x][y] == step && (path[i][j]+d) < path[x][y]) {
				dist[x][y] = step
				path[x][y] = path[i][j] + d
				if x != rh || y != ch {
					q = append(q, []int{x, y})
				}
			}
		}
	}
	if path[rh][ch] == "" {
		return "impossible"
	}
	return path[rh][ch]
}

力扣原题 · Doocs 题解来源

505. 迷宫 II 🔒

中等1 种解法

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

题目、示例与约束

迷宫中有一个球，它有空地 (表示为 0) 和墙 (表示为 1)。球可以向上、向下、向左或向右滚过空地，但直到撞上墙之前它都不会停止滚动。当球停止时，它才可以选择下一个滚动方向。

给定 m × n 的迷宫(maze)，球的起始位置 (start = [startrow, startcol]) 和目的地 (destination = [destinationrow, destinationcol])，返回球在目的地 (destination) 停止的最短距离。如果球不能在目的地 (destination) 停止，返回 -1。

距离是指球从起始位置 ( 不包括 ) 到终点 ( 包括 ) 所经过的空地数。

你可以假设迷宫的边界都是墙 ( 见例子 )。

 

示例 1:

输入: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
输出: 12
解析: 一条最短路径 : left -> down -> left -> down -> right -> down -> right。
             总距离为 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12。

示例 2:

输入: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
输出: -1
解析: 球不可能在目的地停下来。注意，你可以经过目的地，但不能在那里停下来。

示例 3:

输入: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
输出: -1

 

注意:

• m == maze.length
• n == maze[i].length
• 1 <= m, n <= 100
• maze[i][j] 是 0 或 1.
• start.length == 2
• destination.length == 2
• 0 <= startrow, destinationrow < m
• 0 <= startcol, destinationcol < n
• 球和目的地都存在于一个空地中，它们最初不会处于相同的位置。

• 迷宫至少包含两个空地。

方法一：BFS · Go 实现

思考

球会沿一个方向滚到墙边才停下，因此边不是单步网格，而是「一次滚动」。朴素搜索若按格子逐步走，会把同一条滚动重复展开。

状态应是停止点。从起点 BFS，每次向四向滚到尽头，用新路径长度松弛该停止点；更短才入队。由于滚动长度不一，这是按停点松弛的最短路，而不是无权 BFS。到达终点的最短停点距离即为答案，不可达则为 $-1$。

我们定义一个二维数组 $dist$，其中 $dist[i][j]$ 表示从起始位置到达 $(i,j)$ 的最短路径长度。初始时， $dist$ 中的所有元素都被初始化为一个很大的数，除了起始位置，因为起始位置到自身的距离是 $0$。

然后，我们定义一个队列 $q$，将起始位置加入队列。随后不断进行以下操作：弹出队列中的首元素，将其四个方向上可以到达的位置加入队列中，并且在 $dist$ 中记录这些位置的距离，直到队列为空。

最后，如果终点位置的距离仍然是一个很大的数，说明从起始位置无法到达终点位置，返回 $-1$，否则返回终点位置的距离。

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

func shortestDistance(maze [][]int, start []int, destination []int) int {
	m, n := len(maze), len(maze[0])
	dist := make([][]int, m)
	const inf = 1 << 30
	for i := range dist {
		dist[i] = make([]int, n)
		for j := range dist[i] {
			dist[i][j] = inf
		}
	}
	dist[start[0]][start[1]] = 0
	q := [][]int{start}
	dirs := [5]int{-1, 0, 1, 0, -1}
	for len(q) > 0 {
		p := q[0]
		q = q[1:]
		i, j := p[0], p[1]
		for d := 0; d < 4; d++ {
			x, y, k := i, j, dist[i][j]
			a, b := dirs[d], dirs[d+1]
			for x+a >= 0 && x+a < m && y+b >= 0 && y+b < n && maze[x+a][y+b] == 0 {
				x, y, k = x+a, y+b, k+1
			}
			if k < dist[x][y] {
				dist[x][y] = k
				q = append(q, []int{x, y})
			}
		}
	}
	di, dj := destination[0], destination[1]
	if dist[di][dj] == inf {
		return -1
	}
	return dist[di][dj]
}

力扣原题 · Doocs 题解来源

743. 网络延迟时间

中等2 种解法

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

题目、示例与约束

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

 

示例 1：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

示例 2：

输入：times = [[1,2,1]], n = 2, k = 1
输出：1

示例 3：

输入：times = [[1,2,1]], n = 2, k = 2
输出：-1

 

提示：

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• 所有 (ui, vi) 对都 互不相同（即，不含重复边）

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

思考

有向带权图上从 $k$ 出发，使所有节点都收到信号的最短时间，即最长那条最短路。 $n\le 100$，朴素 Dijkstra 的 $O(n^2)$ 可以通过。

每次在未访问点中取当前距离最小者并松弛其出边，与非负边权的最短路标准过程一致。用邻接矩阵存边，无边为 $+\mathrm{\infty }$。

全部松弛后取 $\mathit{\text{dist}}$ 的最大值；若仍为无穷则有点不可达，返回 $-1$。

我们定义 $\mathit{\text{g}}[u][v]$ 表示节点 $u$ 到节点 $v$ 的边权，如果节点 $u$ 到节点 $v$ 之间没有边，则 $\mathit{\text{g}}[u][v]=+\mathrm{\infty }$。

我们维护一个数组 $\mathit{\text{dist}}$，其中 $\mathit{\text{dist}}[i]$ 表示节点 $k$ 到节点 $i$ 的最短路径长度。初始时，我们将 $\mathit{\text{dist}}[i]$ 全部初始化为 $+\mathrm{\infty }$，但 $\mathit{\text{dist}}[k-1]=0$。定义一个数组 $\mathit{\text{vis}}$，其中 $\mathit{\text{vis}}[i]$ 表示节点 $i$ 是否被访问过，初始时，我们将 $\mathit{\text{vis}}[i]$ 全部初始化为 $\text{false}$。

我们每次找到未被访问的距离最小的节点 $t$，然后以节点 $t$ 为中心进行松弛操作，即对于每个节点 $j$，如果 $\mathit{\text{dist}}[j]>\mathit{\text{dist}}[t]+\mathit{\text{g}}[t][j]$，则更新 $\mathit{\text{dist}}[j]=\mathit{\text{dist}}[t]+\mathit{\text{g}}[t][j]$。

最后，我们返回 $\mathit{\text{dist}}$ 中的最大值，即为答案。如果答案为 $+\mathrm{\infty }$，则说明存在无法到达的节点，返回 $-1$。

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

func networkDelayTime(times [][]int, n int, k int) int {
	const inf = 1 << 29
	g := make([][]int, n)
	for i := range g {
		g[i] = make([]int, n)
		for j := range g[i] {
			g[i][j] = inf
		}
	}
	for _, e := range times {
		g[e[0]-1][e[1]-1] = e[2]
	}

	dist := make([]int, n)
	for i := range dist {
		dist[i] = inf
	}
	dist[k-1] = 0

	vis := make([]bool, n)
	for i := 0; i < n; i++ {
		t := -1
		for j := 0; j < n; j++ {
			if !vis[j] && (t == -1 || dist[t] > dist[j]) {
				t = j
			}
		}
		vis[t] = true
		for j := 0; j < n; j++ {
			dist[j] = min(dist[j], dist[t]+g[t][j])
		}
	}

	if ans := slices.Max(dist); ans != inf {
		return ans
	}
	return -1
}

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

思考

方法一每次线性扫点找最小距离，边稀疏时浪费。 $m$ 最多 $6000$，用堆按距离弹出可以降到 $O(m\log m)$。

邻接表存边，优先队列弹出 $(d,u)$，若 $d$ 已不是当前最优则跳过，否则松弛邻居并入堆。答案同样取距离最大值。

我们可以使用优先队列（堆）来优化朴素 Dijkstra 算法。

我们定义 $\mathit{\text{g}}[u]$ 表示节点 $u$ 的所有邻接边，而 $\mathit{\text{dist}}[u]$ 表示节点 $k$ 到节点 $u$ 的最短路径长度。初始时，我们将 $\mathit{\text{dist}}[u]$ 全部初始化为 $+\mathrm{\infty }$，但 $\mathit{\text{dist}}[k-1]=0$。

定义一个优先队列 $\mathit{\text{pq}}$，其中每个元素为 $(\mathit{\text{d}},u)$，表示节点 $u$ 到节点 $k$ 的距离为 $\mathit{\text{d}}$。我们每次从 $\mathit{\text{pq}}$ 中取出距离最小的节点 $(\mathit{\text{d}},u)$。如果 $\mathit{\text{d}}>\mathit{\text{dist}}[u]$，则跳过该节点。否则，我们遍历节点 $u$ 的所有邻接边，对于每个邻接边 $(v,w)$，如果 $\mathit{\text{dist}}[v]>\mathit{\text{dist}}[u]+w$，则更新 $\mathit{\text{dist}}[v]=\mathit{\text{dist}}[u]+w$，并将 $(\mathit{\text{dist}}[v],v)$ 加入 $\mathit{\text{pq}}$。

最后，我们返回 $\mathit{\text{dist}}$ 中的最大值，即为答案。如果答案为 $+\mathrm{\infty }$，则说明存在无法到达的节点，返回 $-1$。

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

func networkDelayTime(times [][]int, n int, k int) int {
	g := make([][][2]int, n)
	for _, e := range times {
		u, v, w := e[0]-1, e[1]-1, e[2]
		g[u] = append(g[u], [2]int{v, w})
	}
	dist := make([]int, n)
	const inf int = 1 << 29
	for i := range dist {
		dist[i] = inf
	}
	dist[k-1] = 0
	pq := hp{{0, k - 1}}
	for len(pq) > 0 {
		p := heap.Pop(&pq).(pair)
		d, u := p.x, p.i
		if d > dist[u] {
			continue
		}
		for _, e := range g[u] {
			v, w := e[0], e[1]
			if nd := d + w; nd < dist[v] {
				dist[v] = nd
				heap.Push(&pq, pair{nd, v})
			}
		}
	}
	if ans := slices.Max(dist); ans < inf {
		return ans
	}
	return -1

}

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

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

力扣原题 · Doocs 题解来源

753. 破解保险箱

困难1 种解法

标签：深度优先搜索、图、字符串、欧拉路径、欧拉回路、欧拉图

题目、示例与约束

有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位都是范围 [0, k - 1] 中的一个数字。

保险箱有一种特殊的密码校验方法，你可以随意输入密码序列，保险箱会自动记住 最后 n 位输入 ，如果匹配，则能够打开保险箱。

• 例如，正确的密码是 "345" ，并且你输入的是 "012345" ：
  • 输入 0 之后，最后 3 位输入是 "0" ，不正确。
  • 输入 1 之后，最后 3 位输入是 "01" ，不正确。
  • 输入 2 之后，最后 3 位输入是 "012" ，不正确。
  • 输入 3 之后，最后 3 位输入是 "123" ，不正确。
  • 输入 4 之后，最后 3 位输入是 "234" ，不正确。
  • 输入 5 之后，最后 3 位输入是 "345" ，正确，打开保险箱。

在只知道密码位数 n 和范围边界 k 的前提下，请你找出并返回确保在输入的 某个时刻 能够打开保险箱的任一 最短 密码序列 。

 

示例 1：

输入：n = 1, k = 2
输出："10"
解释：密码只有 1 位，所以输入每一位就可以。"01" 也能够确保打开保险箱。

示例 2：

输入：n = 2, k = 2
输出："01100"
解释：对于每种可能的密码：
- "00" 从第 4 位开始输入。
- "01" 从第 1 位开始输入。
- "10" 从第 3 位开始输入。
- "11" 从第 2 位开始输入。
因此 "01100" 可以确保打开保险箱。"01100"、"10011" 和 "11001" 也可以确保打开保险箱。

 

提示：

• 1 <= n <= 4
• 1 <= k <= 10
• 1 <= kn <= 4096

方法一：欧拉回路 · Go 实现

思考

要构造最短字符串，使每个长度为 $n$ 的 $k$ 进制串都作为子串出现。总长下界为 $k^n+n-1$，对应德布鲁因序列。

把长 $n-1$ 的串看作点，再接一个字符就是一条边，边即一个密码。每个点出入度均为 $k$，存在欧拉回路，回路上的边序便是最短覆盖。

Hierholzer：从 $0$ 出发，边用整数 $u\cdot 10+x$ 去重，递归走完再把字符追加（后序），最后补上起点的 $n-1$ 个零。

我们可以对题目中所描述的内容构建有向图：将每个点看作一个长度为 $n-1$ 的 $k$ 字符串，每条边都带有一个从 $0$ 到 $k-1$ 的字符。如果点 $u$ 到点 $v$ 之间有一条有向边 $e$，假设 $e$ 携带的字符为 $c$，那么 $u+c$ 的末尾 $k-1$ 个字符形成的字符串等于 $v$，此时边 $u+c$ 就表示了一个长度为 $n$ 的密码。

在这个有向图中，一共有 $k^{n-1}$ 个点，每个点都有 $k$ 条出边，也有 $k$ 条入边，因此，该有向图存在欧拉回路，欧拉回路所经过的路径拼接起来就是题目中的答案。

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

func crackSafe(n int, k int) string {
	mod := int(math.Pow(10, float64(n-1)))
	vis := map[int]bool{}
	ans := &strings.Builder{}
	var dfs func(int)
	dfs = func(u int) {
		for x := 0; x < k; x++ {
			e := u*10 + x
			if !vis[e] {
				vis[e] = true
				v := e % mod
				dfs(v)
				ans.WriteByte(byte('0' + x))
			}
		}
	}
	dfs(0)
	ans.WriteString(strings.Repeat("0", n-1))
	return ans.String()
}

力扣原题 · Doocs 题解来源

787. K 站中转内最便宜的航班

中等2 种解法

标签：深度优先搜索、广度优先搜索、图、动态规划、最短路、堆（优先队列）

题目、示例与约束

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

 

示例 1：

输入: 
n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
输出: 700 
解释: 城市航班图如上
从城市 0 到城市 3 经过最多 1 站的最佳路径用红色标记，费用为 100 + 600 = 700。
请注意，通过城市 [0, 1, 2, 3] 的路径更便宜，但无效，因为它经过了 2 站。

示例 2：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
输出: 200
解释: 
城市航班图如上
从城市 0 到城市 2 经过最多 1 站的最佳路径标记为红色，费用为 100 + 100 = 200。

示例 3：

输入：n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
输出：500
解释：
城市航班图如上
从城市 0 到城市 2 不经过站点的最佳路径标记为红色，费用为 500。

提示：

• 2 <= n <= 100
• 0 <= flights.length <= (n * (n - 1) / 2)
• flights[i].length == 3
• 0 <= fromi, toi < n
• fromi != toi
• 1 <= pricei <= 104
• 航班没有重复，且不存在自环
• 0 <= src, dst, k < n
• src != dst

方法一：Bellman Ford 算法 · Go 实现

思考

最多 $k$ 次中转的最便宜机票，边权非负但中转限制使普通 Dijkstra 要带上剩余步数。 $n\le 100$，限制松弛轮次的 Bellman-Ford 更直接。

最多 $k$ 次中转即最多 $k+1$ 条边。每轮用上一轮的距离备份松弛，避免同一轮内走多条边。

$k+1$ 轮后 $dist[dst]$ 若仍为无穷则无解。

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
	const inf = 0x3f3f3f3f
	dist := make([]int, n)
	backup := make([]int, n)
	for i := range dist {
		dist[i] = inf
	}
	dist[src] = 0
	for i := 0; i < k+1; i++ {
		copy(backup, dist)
		for _, e := range flights {
			f, t, p := e[0], e[1], e[2]
			dist[t] = min(dist[t], backup[f]+p)
		}
	}
	if dist[dst] == inf {
		return -1
	}
	return dist[dst]
}

方法二：DFS + 记忆化搜索 · Go 实现

思考

Bellman-Ford 枚举全部边。从 $src$ 出发、还剩 $k$ 条边时的最小花费也可记忆化搜索：到达 $dst$ 为 $0$，边用尽为无穷。

$dfs(u,k)$ 枚举出边。边数仍是 $k+1$（含出发）。状态 $O(nk)$。

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
	n += 10
	memo := make([][]int, n)
	g := make([][]int, n)
	for i := range memo {
		memo[i] = make([]int, n)
		g[i] = make([]int, n)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}

	for _, e := range flights {
		g[e[0]][e[1]] = e[2]
	}
	inf := int(1e6)
	var dfs func(u, k int) int
	dfs = func(u, k int) int {
		if memo[u][k] != -1 {
			return memo[u][k]
		}
		if u == dst {
			return 0
		}
		if k <= 0 {
			return inf
		}
		ans := inf
		for v, p := range g[u] {
			if p > 0 {
				ans = min(ans, dfs(v, k-1)+p)
			}
		}
		memo[u][k] = ans
		return ans
	}
	ans := dfs(src, k+1)
	if ans >= inf {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源

797. 所有可能的路径

中等1 种解法

标签：深度优先搜索、广度优先搜索、图、回溯、有向无环图

题目、示例与约束

给你一个有 n 个节点的 有向无环图（DAG），请你找出从节点 0 到节点 n-1 的所有路径并输出（不要求按特定顺序）

 graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

 

示例 1：

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

示例 2：

输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

 

提示：

• n == graph.length
• 2 <= n <= 15
• 0 <= graph[i][j] < n
• graph[i][j] != i（即不存在自环）
• graph[i] 中的所有元素 互不相同
• 保证输入为 有向无环图（DAG）

 

方法一：BFS · Go 实现

思考

有向无环图上枚举 $0$ 到 $n-1$ 的全部路径。 $n\le 15$，路径数可到指数级，但必须全部输出，广搜或深搜都可以。

队列保存整条路径，弹出后若终点则收入答案，否则把每个后继接在后面再入队。

从结点 $0$ 出发，用队列保存路径，到达 $n-1$ 时记入答案。

func allPathsSourceTarget(graph [][]int) [][]int {
	var path []int
	path = append(path, 0)
	var ans [][]int

	var dfs func(i int)
	dfs = func(i int) {
		if i == len(graph)-1 {
			ans = append(ans, append([]int(nil), path...))
			return
		}
		for _, j := range graph[i] {
			path = append(path, j)
			dfs(j)
			path = path[:len(path)-1]
		}
	}

	dfs(0)
	return ans
}

力扣原题 · Doocs 题解来源

802. 找到最终的安全状态

中等2 种解法

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

题目、示例与约束

有一个有 n 个节点的有向图，节点按 0 到 n - 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph表示， graph[i]是与节点 i 相邻的节点的整数数组，这意味着从节点 i 到 graph[i]中的每个节点都有一条边。

如果一个节点没有连出的有向边，则该节点是 终端节点 。如果从该节点开始的所有可能路径都通向 终端节点（或另一个安全节点），则该节点为 安全节点。

返回一个由图中所有 安全节点 组成的数组作为答案。答案数组中的元素应当按 升序 排列。

 

示例 1：

输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
解释：示意图如上。
节点 5 和节点 6 是终端节点，因为它们都没有出边。
从节点 2、4、5 和 6 开始的所有路径都指向节点 5 或 6 。

示例 2：

输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出：[4]
解释:
只有节点 4 是终端节点，从节点 4 开始的所有路径都通向节点 4 。

 

提示：

• n == graph.length
• 1 <= n <= 104
• 0 <= graph[i].length <= n
• 0 <= graph[i][j] <= n - 1
• graph[i] 按严格递增顺序排列。
• 图中可能包含自环。
• 图中边的数目在范围 [1, 4 * 104] 内。

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

思考

最终安全点是出发后必然进入出度为 $0$ 的结点、且途中不进入环的点。对每个点沿出边搜索是否能走到环，会在同一条链上重复遍历。

将边反向后，原图出度变为入度。从入度为 $0$ 的点做拓扑删除，能被删掉的点恰好是无法走到环的点，亦即安全点。 $n\le {10}^4$ 时一次线性遍历即可。

出度为零的点是安全的，如果一个点只能到达安全的点，那么它同样是安全的，所以问题转换成了拓扑排序。

我们可以将图中所有边反向，得到一个反图，然后在反图上运行拓扑排序。

时间复杂度 $O(n+m)$，其中 $n$ 表示图中的点数， $m$ 表示图中的边数。

func eventualSafeNodes(graph [][]int) []int {
	n := len(graph)
	indeg := make([]int, n)
	rg := make([][]int, n)
	q := []int{}
	for i, vs := range graph {
		for _, j := range vs {
			rg[j] = append(rg[j], i)
		}
		indeg[i] = len(vs)
		if indeg[i] == 0 {
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		i := q[0]
		q = q[1:]
		for _, j := range rg[i] {
			indeg[j]--
			if indeg[j] == 0 {
				q = append(q, j)
			}
		}
	}
	ans := []int{}
	for i, v := range indeg {
		if v == 0 {
			ans = append(ans, i)
		}
	}
	return ans
}

方法二：DFS + 三色标记法 · Go 实现

思考

拓扑排序需要建反图并维护入度。若希望沿原图直接判定，可用三色标记做一次 DFS：访问中的灰色表示当前路径成环，递归结束后标为黑色表示从该点出发皆安全。

空间上不再需要反图，答案由「该点 DFS 返回真」筛出，复杂度同为线性。

若起始节点位于一个环内，或者能到达一个环，则该节点不是安全的。否则，该节点是安全的。

• 白色（用 0 表示）：该节点尚未被访问；
• 灰色（用 1 表示）：该节点位于递归栈中，或者在某个环上；
• 黑色（用 2 表示）：该节点搜索完毕，是一个安全节点。

func eventualSafeNodes(graph [][]int) []int {
	n := len(graph)
	color := make([]int, n)
	var dfs func(int) bool
	dfs = func(i int) bool {
		if color[i] > 0 {
			return color[i] == 2
		}
		color[i] = 1
		for _, j := range graph[i] {
			if !dfs(j) {
				return false
			}
		}
		color[i] = 2
		return true
	}
	ans := []int{}
	for i := range graph {
		if dfs(i) {
			ans = append(ans, i)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

834. 树中距离之和

困难2 种解法

标签：树、深度优先搜索、图、动态规划、树形 DP

题目、示例与约束

给定一个无向、连通的树。树中有 n 个标记为 0...n-1 的节点以及 n-1 条边 。

给定整数 n 和数组 edges ， edges[i] = [ai, bi]表示树中的节点 ai 和 bi 之间有一条边。

返回长度为 n 的数组 answer ，其中 answer[i] 是树中第 i 个节点与所有其他节点之间的距离之和。

 

示例 1:

输入: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
输出: [8,12,6,10,10,10]
解释: 树如图所示。
我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) 
也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此类推。

示例 2:

输入: n = 1, edges = []
输出: [0]

示例 3:

输入: n = 2, edges = [[1,0]]
输出: [1,1]

 

提示:

• 1 <= n <= 3 * 104
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• 给定的输入保证为有效的树

方法一：树形 DP（换根） · Go 实现

思考

对每个结点求到其余结点的距离和。 $n\le 3\cdot {10}^4$，若以每个点为根做一次 DFS 会平方级。换根后，相邻两点的答案只差「子树大小」与「树外点数」。

先以 $0$ 为根算出 $ans[0]$ 及各子树大小，再第二次 DFS 用 $t-\mathit{\text{size}}[j]+n-\mathit{\text{size}}[j]$ 推到孩子。两遍遍历得到全部答案。

我们先跑一遍 DFS，计算出每个节点的子树大小，记录在数组 $size$ 中，并且统计出节点 $0$ 到其他节点的距离之和，记录在 $ans[0]$ 中。

接下来，我们再跑一遍 DFS，枚举每个点作为根节点时，其他节点到根节点的距离之和。假设当前节点 $i$ 的答案为 $t$，当我们从节点 $i$ 转移到节点 $j$ 时，距离之和变为 $t-size[j]+n-size[j]$，即距离节点 $j$ 及其子树节点的距离之和减少 $size[j]$，而距离其它节点的距离之和增加 $n-size[j]$。

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

相似题目：

• 2581. 统计可能的树根数目

func sumOfDistancesInTree(n int, edges [][]int) []int {
	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)
	}
	ans := make([]int, n)
	size := make([]int, n)
	var dfs1 func(i, fa, d int)
	dfs1 = func(i, fa, d int) {
		ans[0] += d
		size[i] = 1
		for _, j := range g[i] {
			if j != fa {
				dfs1(j, i, d+1)
				size[i] += size[j]
			}
		}
	}
	var dfs2 func(i, fa, t int)
	dfs2 = func(i, fa, t int) {
		ans[i] = t
		for _, j := range g[i] {
			if j != fa {
				dfs2(j, i, t-size[j]+n-size[j])
			}
		}
	}
	dfs1(0, -1, 0)
	dfs2(0, -1, ans[0])
	return ans
}

方法二：换根 DP + 显式栈 · Go 实现

思考

对每个结点求到其余结点的距离和。 $n\le 3\cdot {10}^4$，以每个点为根各做一次遍历会平方级；换根后，相邻两点的答案只差子树大小与树外点数。沿一条链递归时调用深度等于 $n$，链长达到 $1000$ 就会超出 Python 的递归上限。子树大小要等孩子算完才能相加，所以第一遍用带状态的栈做后序：状态 $0$ 累加深度并压入孩子，状态 $1$ 汇总 $size$。第二遍答案只依赖父亲的答案和已经算好的 $size$，用栈按前序把 $t-size[j]+n-size[j]$ 传给孩子。

先以 $0$ 为根做后序遍历。栈里存放节点、父亲、深度和状态。状态为 $0$ 时，把深度累加到 $ans[0]$，再把同一节点以状态 $1$ 压回，并压入每个孩子。状态为 $1$ 时，孩子的子树大小都已写好， $size[i]$ 等于 $1$ 加上各孩子的 $size$。

接着用显式栈做换根。栈里初始是 $(0,-1,ans[0])$。弹出节点 $i$ 时把当前距离和 $t$ 写入 $ans[i]$。从 $i$ 走到孩子 $j$ 时，距离 $j$ 及其子树的距离和减少 $size[j]$，距离其余节点的距离和增加 $n-size[j]$，所以压入的新距离和是 $t-size[j]+n-size[j]$。

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

相似题目：

• 2581. 统计可能的树根数目

func sumOfDistancesInTree(n int, edges [][]int) []int {
	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)
	}
	ans := make([]int, n)
	size := make([]int, n)
	type frame struct{ i, fa, d, state int }
	stk := []frame{{0, -1, 0, 0}}
	for len(stk) > 0 {
		f := stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		if f.state == 0 {
			ans[0] += f.d
			stk = append(stk, frame{f.i, f.fa, f.d, 1})
			for _, j := range g[f.i] {
				if j != f.fa {
					stk = append(stk, frame{j, f.i, f.d + 1, 0})
				}
			}
		} else {
			size[f.i] = 1
			for _, j := range g[f.i] {
				if j != f.fa {
					size[f.i] += size[j]
				}
			}
		}
	}
	type step struct{ i, fa, t int }
	walk := []step{{0, -1, ans[0]}}
	for len(walk) > 0 {
		f := walk[len(walk)-1]
		walk = walk[:len(walk)-1]
		ans[f.i] = f.t
		for _, j := range g[f.i] {
			if j != f.fa {
				walk = append(walk, step{j, f.i, f.t - size[j] + n - size[j]})
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

841. 钥匙和房间

中等3 种解法

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

题目、示例与约束

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套 不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。

 

示例 1：

输入：rooms = [[1],[2],[3],[]]
输出：true
解释：
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

示例 2：

输入：rooms = [[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

 

提示：

• n == rooms.length
• 2 <= n <= 1000
• 0 <= rooms[i].length <= 1000
• 1 <= sum(rooms[i].length) <= 3000
• 0 <= rooms[i][j] < n
• 所有 rooms[i] 的值 互不相同

方法一：DFS · Go 实现

思考

房间构成有向图，钥匙即出边，问从 $0$ 出发能否到达全部房间。 $n\le 1000$，一次图遍历即可。

DFS 从 $0$ 沿钥匙深入，访问集合大小等于房间数则成功。

我们可以使用深度优先搜索的方法遍历整张图，统计可以到达的节点个数，并利用数组 vis 标记当前节点是否访问过，以防止重复访问。

最后统计访问过的节点个数，若与节点总数相同则说明可以访问所有节点，否则说明存在无法到达的节点。

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

func canVisitAllRooms(rooms [][]int) bool {
	n := len(rooms)
	cnt := 0
	vis := make([]bool, n)
	var dfs func(int)
	dfs = func(i int) {
		if vis[i] {
			return
		}
		vis[i] = true
		cnt++
		for _, j := range rooms[i] {
			dfs(j)
		}
	}
	dfs(0)
	return cnt == n
}

方法二：BFS · Go 实现

思考

方法一用显式栈沿钥匙扩展。同一可达性也可以用队列：从 $0$ 开始，取出一把钥匙后把尚未访问的房间入队。访问标记同样去掉重复钥匙，最后比较访问数与 $n$。

我们也可以使用广度优先搜索的方法遍历整张图，用一个哈希表或者数组 vis 标记当前节点是否访问过，以防止重复访问。

具体地，我们定义一个队列 $q$，初始时将节点 $0$ 放入队列中，然后不断遍历队列。每次取出队首节点 $i$，如果 $i$ 被访问过则直接跳过，否则我们将其标记为已访问，然后将 $i$ 可以到达的节点加入队列中。

最后统计访问过的节点个数，若与节点总数相同则说明可以访问所有节点，否则说明存在无法到达的节点。

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

func canVisitAllRooms(rooms [][]int) bool {
	n := len(rooms)
	vis := make([]bool, n)
	cnt := 0
	q := []int{0}
	for len(q) > 0 {
		i := q[0]
		q = q[1:]
		if vis[i] {
			continue
		}
		vis[i] = true
		cnt++
		for _, j := range rooms[i] {
			q = append(q, j)
		}
	}
	return cnt == n
}

方法三：显式栈 · Go 实现

思考

房间构成有向图，每把钥匙是一条出边，问从 $0$ 出发能否到达全部房间。 $n\le 1000$，一次遍历就够。沿一条钥匙链递归时，调用深度等于房间数，链长达到 $1000$ 就会超出 Python 的递归上限。因此用栈保存待开的房间：弹出后若尚未访问就标记，再把该房间里的钥匙压入。同一房间可能被多把钥匙重复压入，标记保证只展开一次。访问过的房间数等于 $n$ 时就能打开全部门。

从房间 $0$ 开始，用显式栈遍历能到达的房间。栈里初始只有 $0$。弹出房间 $i$ 时，如果它已经访问过就跳过；否则标记为已访问，并把 $i$ 中的每把钥匙对应的房间压入栈。重复的钥匙只会让同一房间再次入栈，弹出时会被跳过。

最后检查是否每个房间都被访问过。全部访问过就返回 true，否则存在无法到达的房间。

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

func canVisitAllRooms(rooms [][]int) bool {
	n := len(rooms)
	vis := make([]bool, n)
	stk := []int{0}
	for len(stk) > 0 {
		i := stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		if vis[i] {
			continue
		}
		vis[i] = true
		for _, j := range rooms[i] {
			stk = append(stk, j)
		}
	}
	for _, v := range vis {
		if !v {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

847. 访问所有节点的最短路径

困难1 种解法

标签：位运算、广度优先搜索、图、动态规划、位掩码

题目、示例与约束

存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。

给你一个数组 graph 表示这个图。其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。

返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

 

示例 1：

输入：graph = [[1,2,3],[0],[0],[0]]
输出：4
解释：一种可能的路径为 [1,0,2,0,3]

示例 2：

输入：graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一种可能的路径为 [0,1,4,2,3]

 

提示：

• n == graph.length
• 1 <= n <= 12
• 0 <= graph[i].length < n
• graph[i] 不包含 i
• 如果 graph[a] 包含 b ，那么 graph[b] 也包含 a
• 输入的图总是连通图

方法一：状态压缩 + BFS · Go 实现

思考

求访问所有结点的最短路，边可重复走。 $n\le 12$，路径本身不能当状态，但「当前点 + 已访问集合」只有 $n\cdot 2^n$ 个。

从每个点出发做状态压缩 BFS，状态 $(i,\mathit{\text{mask}})$ 表示位于 $i$ 且访问集合为 $\mathit{\text{mask}}$。首次使 $\mathit{\text{mask}}$ 为全集的层数即最短长度。

我们注意到 $n$ 的范围不超过 $12$，因此，我们可以用一个 $12$ 位的二进制数来表示每个节点的访问情况，其中第 $i$ 位为 $1$ 表示第 $i$ 个节点已经被访问过，为 $0$ 表示该节点还没有被访问过。

我们初始化队列 $q$，其中每个元素是一个二元素 $(i,st)$，表示当前位于节点 $i$，且已经遍历过的节点的集合为 $st$。初始时，队列中只有 $n$ 个元素，即 $(i,2^i)$，表示可以从任一节点出发开始遍历。另外，我们用一个哈希表或数组 $vis$ 记录每个状态是否已经被搜索过，防止无效的重复搜索。

在 BFS 的过程中，我们每次取出队首元素 $(i,st)$，如果当前 $st$ 包含 $n$ 个 $1$，那么我们就找到了一条从起点出发的遍历路径，返回当前的步数即可。否则我们枚举当前节点 $i$ 的所有连边 $(i,j)$，如果 $(j,st\vee 2^j)$ 没有被搜索过，那么就将 $(j,st\vee 2^j)$ 加入队列 $q$ 中，并且用 $vis$ 记录它已经被搜索过。循环此过程，直到找到一条路径。

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

func shortestPathLength(graph [][]int) int {
	n := len(graph)
	q := [][2]int{}
	vis := make([][]bool, n)
	for i := range vis {
		vis[i] = make([]bool, 1<<n)
		vis[i][1<<i] = true
		q = append(q, [2]int{i, 1 << i})
	}
	for ans := 0; ; ans++ {
		for k := len(q); k > 0; k-- {
			p := q[0]
			q = q[1:]
			i, st := p[0], p[1]
			if st == (1<<n)-1 {
				return ans
			}
			for _, j := range graph[i] {
				nst := st | 1<<j
				if !vis[j][nst] {
					vis[j][nst] = true
					q = append(q, [2]int{j, nst})
				}
			}
		}
	}
}

力扣原题 · Doocs 题解来源

851. 喧闹和富有

中等1 种解法

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

题目、示例与约束

有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为 x 的人简称为 "person x "。

给你一个数组 richer ，其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有钱。另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值。richer 中所给出的数据 逻辑自洽（也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x 更有钱的情况 ）。

现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是，在所有拥有的钱肯定不少于 person x 的人中，person y 是最不安静的人（也就是安静值 quiet[y] 最小的人）。

 

示例 1：

输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
输出：[5,5,2,5,4,5,6,7]
解释： 
answer[0] = 5，
person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。
唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7，
但是目前还不清楚他是否比 person 0 更有钱。
answer[7] = 7，
在所有拥有的钱肯定不少于 person 7 的人中（这可能包括 person 3，4，5，6 以及 7），
最安静（有较低安静值 quiet[x]）的人是 person 7。
其他的答案也可以用类似的推理来解释。

示例 2：

输入：richer = [], quiet = [0]
输出：[0]

 

提示：

• n == quiet.length
• 1 <= n <= 500
• 0 <= quiet[i] < n
• quiet 的所有值 互不相同
• 0 <= richer.length <= n * (n - 1) / 2
• 0 <= ai, bi < n
• ai != bi
• richer 中的所有数对 互不相同
• 对 richer 的观察在逻辑上是一致的

方法一：DFS · Go 实现

思考

在「更富有」构成的 DAG 上，每人要找自己及所有更富者中最安静的人。 $n\le 500$，对每个人做一次搜索会重复走同一子图。

建从穷人指向富人的边，记忆化 DFS：答案先取自己，再与所有更富邻居的答案比安静值。每个点只算一次，再按编号输出。

我们先用邻接表 $g$ 存储 $richer$ 数组中的信息，其中 $g[i]$ 表示所有比 $i$ 更有钱的人的集合。

然后对于每个人 $i$，我们用 DFS 遍历所有比 $i$ 更有钱的人，找到其中安静值最小的人，即为答案。

时间复杂度 $O(m+n)$，空间复杂度 $O(m+n)$。其中 $m$ 和 $n$ 分别为 $richer$ 数组和 $quiet$ 数组的长度。

func loudAndRich(richer [][]int, quiet []int) []int {
	n := len(quiet)
	g := make([][]int, n)
	ans := make([]int, n)
	for i := range g {
		ans[i] = -1
	}
	for _, r := range richer {
		a, b := r[0], r[1]
		g[b] = append(g[b], a)
	}
	var dfs func(int)
	dfs = func(i int) {
		if ans[i] != -1 {
			return
		}
		ans[i] = i
		for _, j := range g[i] {
			dfs(j)
			if quiet[ans[j]] < quiet[ans[i]] {
				ans[i] = ans[j]
			}
		}
	}
	for i := range ans {
		dfs(i)
	}
	return ans
}

力扣原题 · Doocs 题解来源

882. 细分图中的可到达节点

困难1 种解法

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

题目、示例与约束

给你一个无向图（原始图），图中有 n 个节点，编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链，每条边之间的新节点数各不相同。

图用由边组成的二维数组 edges 表示，其中 edges[i] = [ui, vi, cnti] 表示原始图中节点 ui 和 vi 之间存在一条边，cnti 是将边 细分 后的新节点总数。注意，cnti == 0 表示边不可细分。

要 细分 边 [ui, vi] ，需要将其替换为 (cnti + 1) 条新边，和 cnti 个新节点。新节点为 x1, x2, ..., xcnti ，新边为 [ui, x1], [x1, x2], [x2, x3], ..., [xcnti-1, xcnti], [xcnti, vi] 。

现在得到一个 新的细分图 ，请你计算从节点 0 出发，可以到达多少个节点？如果节点间距离是 maxMoves 或更少，则视为 可以到达 。

给你原始图和 maxMoves ，返回 新的细分图中从节点 0 出发 可到达的节点数 。

 

示例 1：

输入：edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
输出：13
解释：边的细分情况如上图所示。
可以到达的节点已经用黄色标注出来。

示例 2：

输入：edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
输出：23

示例 3：

输入：edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n = 5
输出：1
解释：节点 0 与图的其余部分没有连通，所以只有节点 0 可以到达。

 

提示：

• 0 <= edges.length <= min(n * (n - 1) / 2, 104)
• edges[i].length == 3
• 0 <= ui < vi < n
• 图中 不存在平行边
• 0 <= cnti <= 104
• 0 <= maxMoves <= 109
• 1 <= n <= 3000

方法一：Dijkstra 算法 · Go 实现

思考

原图每条边被细分成 $\mathit{\text{cnt}}$ 个新点，问从 $0$ 出发在 $\mathit{\text{maxMoves}}$ 步内能到达多少点。细分点极多，不能建出显式图。

把边权当作 $\mathit{\text{cnt}}+1$，对原图结点跑 Dijkstra，得到到达各原结点的最短路。原结点可达则计数；边上的细分点由两端剩余步数夹逼，不超过 $\mathit{\text{cnt}}$。

这道题本质是求从节点 $0$ 出发，最多经过 $maxMoves$ 步，可以到达多少个节点。单源最短路，且边权非负，我们可以考虑使用 Dijkstra 算法。

根据题目描述，节点 $u_i$ 到节点 $v_i$ 之间存在 $cn{t}_i$ 个新节点，那么节点 $u_i$ 到节点 $v_i$ 的距离为 $cn{t}_i+1$。

我们举个简单的例子，以下节点 $1$ 和节点 $2$ 之间存在 $3$ 个新节点，那么节点 $1$ 到节点 $2$ 之间有 $4$ 条边，也即距离为 $4$。

1 -- o -- o -- o -- 2

因此，我们可以将原图中两点之间新节点的个数 $cn{t}_i$ 加 $1$，得到两点之间的距离。然后构建一个邻接表 $g$，用于存储每个节点的邻接节点以及到达邻接节点的距离。

接下来，我们使用 Dijkstra 算法求出从节点 $0$ 到原始图其余所有节点的最短距离，存储在数组 $dist$ 中。

然后，我们遍历数组 $dist$，统计其中小于等于 $maxMoves$ 的节点个数，也就是我们可以到达的节点数。不过，这并不是最终答案，我们还需要加上新节点中符合条件的节点个数。

我们可以发现，如果我们能在 $dist[u]$ 步到达节点 $u$（其中 $dist[u]\le maxMoves$），并且节点 $u$ 到节点 $v$ 之间有 $cnt$ 个新节点，那么我们能通过节点 $u$ 到达的新节点个数 $a=min(cnt,maxMoves-dist[u])$。同理，我们能通过节点 $v$ 到达的新节点个数 $b=min(cnt,maxMoves-dist[v])$。那么，我们能到达节点 $u$ 和节点 $v$ 之间的新节点个数为 $min(cnt,a+b)$。

因此，我们再遍历所有的边，统计其中能到达的新节点个数，累加到答案中即可。

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

func reachableNodes(edges [][]int, maxMoves int, n int) (ans int) {
	g := make([][]pair, n)
	for _, e := range edges {
		u, v, cnt := e[0], e[1], e[2]+1
		g[u] = append(g[u], pair{cnt, v})
		g[v] = append(g[v], pair{cnt, u})
	}
	dist := make([]int, n)
	for i := range dist {
		dist[i] = 1 << 30
	}
	dist[0] = 0
	q := hp{{0, 0}}
	for len(q) > 0 {
		p := heap.Pop(&q).(pair)
		d, u := p.v, p.i
		for _, nxt := range g[u] {
			v, cnt := nxt.i, nxt.v
			if t := d + cnt; t < dist[v] {
				dist[v] = t
				heap.Push(&q, pair{t, v})
			}
		}
	}
	for _, d := range dist {
		if d <= maxMoves {
			ans++
		}
	}
	for _, e := range edges {
		u, v, cnt := e[0], e[1], e[2]
		a := min(cnt, max(0, maxMoves-dist[u]))
		b := min(cnt, max(0, maxMoves-dist[v]))
		ans += min(cnt, a+b)
	}
	return
}

type pair struct{ v, i int }
type hp []pair

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

力扣原题 · Doocs 题解来源

913. 猫和老鼠

困难1 种解法

标签：图、拓扑排序、记忆化、极小化极大、数学、动态规划、博弈、零和博弈

题目、示例与约束

两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。

图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。

老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。

在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。

此外，猫无法移动到洞中（节点 0）。

然后，游戏在出现以下三种情形之一时结束：

• 如果猫和老鼠出现在同一个节点，猫获胜。
• 如果老鼠到达洞中，老鼠获胜。
• 如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。

给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：

• 如果老鼠获胜，则返回 1；
• 如果猫获胜，则返回 2；
• 如果平局，则返回 0 。

 

示例 1：

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

示例 2：

输入：graph = [[1,3],[0],[3],[0,2]]
输出：1

 

提示：

• 3 <= graph.length <= 50
• 1 <= graph[i].length < graph.length
• 0 <= graph[i][j] < graph.length
• graph[i][j] != i
• graph[i] 互不相同
• 猫和老鼠在游戏中总是可以移动

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

思考

状态为（鼠位、猫位、轮到谁）， $n\le 50$，正向搜索难以及时判定平局。从终局反推：鼠入洞则鼠胜，同格则猫胜。

上一状态若轮到的一方能走进己方必胜，则记为该方胜；否则将出度减一，减尽后记为对方胜。按此拓扑序扫完后读取初始状态 $(1,2,\text{鼠回合})$。

根据题目描述，游戏中的状态由老鼠的位置、猫的位置和移动方决定。当状态为以下情况，可以直接确定胜负：

• 当猫和老鼠的位置相同时，猫获胜，这是猫的必胜状态，老鼠的必败状态。
• 当老鼠位于洞时，老鼠获胜，这是老鼠的必胜状态，猫的必败状态。

为了得到初始状态的游戏结果，需要从边界状态开始遍历所有的状态。每个状态包含老鼠的位置、猫的位置和移动方，根据当前状态可以得到上一轮的所有可能状态，上一轮状态的移动方和当前状态的移动方相反，上一轮状态的移动方在上一轮状态的位置和当前状态的位置不同。

我们用元组 $(m,c,t)$ 表示本轮的状态，用 $(pm,pc,pt)$ 表示上一轮可能的状态，那么上一轮的所有可能状态有：

• 如果本轮的移动方是老鼠，那么上一轮的移动方是猫，上一轮的老鼠位置是本轮老鼠位置，上一轮的猫位置是本轮猫位置的所有邻接点。
• 如果本轮的移动方是猫，那么上一轮的移动方是老鼠，上一轮的猫位置是本轮猫位置，上一轮的老鼠位置是本轮老鼠位置的所有邻接点。

初始时，除了边界状态以外，其他所有状态的结果都是未知的。我们从边界状态开始，对于每个状态，得到上一轮的所有可能状态并更新结果，更新的逻辑如下：

1. 如果上一轮的移动方与本轮的获胜方相同，那么上一轮的移动方可以到达当前状态并获胜，直接更新上一轮的状态为本轮的获胜方。
2. 如果上一轮的移动方与本轮的获胜方不同，且上一轮的移动方可以到达的所有状态都是上一轮的移动方的必败状态，那么我们将上一轮的状态更新为本轮的获胜方。

对于第 $2$ 个更新逻辑，我们需要记录每个状态的度。初始时，每个状态的度表示该状态的移动方可以移动到的结点数，即移动方所在节点的相邻结点数，如果移动方是猫且所在结点与洞相邻则需要将该状态的度减 $1$。

当所有状态的结果都更新完毕时，初始状态的结果即为最终结果。

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

const (
	hole       = 0
	mouseStart = 1
	catStart   = 2
	mouseTurn  = 0
	catTurn    = 1
	mouseWin   = 1
	catWin     = 2
	tie        = 0
)

func catMouseGame(graph [][]int) int {
	ans := [50][50][2]int{}
	degree := [50][50][2]int{}
	n := len(graph)
	for i := 0; i < n; i++ {
		for j := 1; j < n; j++ {
			degree[i][j][mouseTurn] = len(graph[i])
			degree[i][j][catTurn] = len(graph[j])
		}
		for _, j := range graph[hole] {
			degree[i][j][catTurn]--
		}
	}
	type tuple struct{ m, c, t int }
	q := []tuple{}
	for j := 1; j < n; j++ {
		ans[0][j][mouseTurn], ans[0][j][catTurn] = mouseWin, mouseWin
		q = append(q, tuple{0, j, mouseTurn})
		q = append(q, tuple{0, j, catTurn})
	}
	for i := 1; i < n; i++ {
		ans[i][i][mouseTurn], ans[i][i][catTurn] = catWin, catWin
		q = append(q, tuple{i, i, mouseTurn})
		q = append(q, tuple{i, i, catTurn})
	}
	getPrevStates := func(m, c, t int) []tuple {
		pre := []tuple{}
		pt := t ^ 1
		if pt == catTurn {
			for _, pc := range graph[c] {
				if pc != hole {
					pre = append(pre, tuple{m, pc, pt})
				}
			}
		} else {
			for _, pm := range graph[m] {
				pre = append(pre, tuple{pm, c, pt})
			}
		}
		return pre
	}
	for len(q) > 0 {
		state := q[0]
		m, c, t := state.m, state.c, state.t
		q = q[1:]
		x := ans[m][c][t]
		for _, prevState := range getPrevStates(m, c, t) {
			pm, pc, pt := prevState.m, prevState.c, prevState.t
			if ans[pm][pc][pt] == tie {
				win := (x == mouseWin && pt == mouseTurn) || (x == catWin && pt == catTurn)
				if win {
					ans[pm][pc][pt] = x
					q = append(q, tuple{pm, pc, pt})
				} else {
					degree[pm][pc][pt]--
					if degree[pm][pc][pt] == 0 {
						ans[pm][pc][pt] = x
						q = append(q, tuple{pm, pc, pt})
					}
				}
			}
		}
	}
	return ans[mouseStart][catStart][mouseTurn]
}

力扣原题 · Doocs 题解来源

997. 找到小镇的法官

简单1 种解法

标签：图、数组、哈希表

题目、示例与约束

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。

如果小镇法官真的存在，那么：

1. 小镇法官不会信任任何人。
2. 每个人（除了小镇法官）都信任这位小镇法官。
3. 只有一个人同时满足属性 1 和属性 2 。

给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。

 

示例 1：

输入：n = 2, trust = [[1,2]]
输出：2

示例 2：

输入：n = 3, trust = [[1,3],[2,3]]
输出：3

示例 3：

输入：n = 3, trust = [[1,3],[2,3],[3,1]]
输出：-1

 

提示：

• 1 <= n <= 1000
• 0 <= trust.length <= 104
• trust[i].length == 2
• trust 中的所有trust[i] = [ai, bi] 互不相同
• ai != bi
• 1 <= ai, bi <= n

方法一：计数 · Go 实现

思考

法官不信任任何人且被其余 $n-1$ 人信任。建图找入度 $n-1$、出度 $0$ 的点即可。两次数组分别统计信任与被信任次数，一次扫描 $trust$ 后检查每个编号。

我们创建两个长度为 $n+1$ 的数组 $cnt1$ 和 $cnt2$，分别表示每个人信任的人数和被信任的人数。

接下来，我们遍历数组 $trust$，对于每一项 $[a_i,b_i]$，我们将 $cnt1[a_i]$ 和 $cnt2[b_i]$ 分别加 $1$。

最后，我们在 $[1,..n]$ 范围内枚举每个人 $i$，如果 $cnt1[i]=0$ 且 $cnt2[i]=n-1$，则说明 $i$ 是小镇法官，返回 $i$ 即可。否则遍历结束后，返回 $-1$。

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

func findJudge(n int, trust [][]int) int {
	cnt1 := make([]int, n+1)
	cnt2 := make([]int, n+1)
	for _, t := range trust {
		a, b := t[0], t[1]
		cnt1[a]++
		cnt2[b]++
	}
	for i := 1; i <= n; i++ {
		if cnt1[i] == 0 && cnt2[i] == n-1 {
			return i
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

1042. 不邻接植花

中等1 种解法

标签：深度优先搜索、广度优先搜索、图、图的着色

题目、示例与约束

有 n 个花园，按从 1 到 n 标记。另有数组 paths ，其中 paths[i] = [xi, yi] 描述了花园 xi 到花园 yi 的双向路径。在每个花园中，你打算种下四种花之一。

另外，所有花园 最多 有 3 条路径可以进入或离开.

你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。

以数组形式返回 任一 可行的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用  1、2、3、4 表示。保证存在答案。

 

示例 1：

输入：n = 3, paths = [[1,2],[2,3],[3,1]]
输出：[1,2,3]
解释：
花园 1 和 2 花的种类不同。
花园 2 和 3 花的种类不同。
花园 3 和 1 花的种类不同。
因此，[1,2,3] 是一个满足题意的答案。其他满足题意的答案有 [1,2,4]、[1,4,2] 和 [3,2,1]

示例 2：

输入：n = 4, paths = [[1,2],[3,4]]
输出：[1,2,1,2]

示例 3：

输入：n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出：[1,2,3,4]

 

提示：

• 1 <= n <= 104
• 0 <= paths.length <= 2 * 104
• paths[i].length == 2
• 1 <= xi, yi <= n
• xi != yi
• 每个花园 最多 有 3 条路径可以进入或离开

方法一：枚举 · Go 实现

思考

每个花园至多三条边，四种花，四色定理保证可染，不必回溯搜索。按编号依次给尚未使用的颜色即可。

先建邻接表，对花园 $x$ 收集邻居已用颜色，再在 $1..4$ 中取一个未用的写入。

一度至多为 $3$，总能找到一种颜色，一遍线性扫完。

我们先根据数组 $\mathit{\text{paths}}$ 构建图 $g$，其中 $g[x]$ 表示与花园 $x$ 相邻的花园列表。

接下来，对于每个花园 $x$，我们先找出与 $x$ 相邻的花园 $y$，并将 $y$ 花园中种植的花的种类标记为已使用。然后我们从花的种类 $1$ 开始枚举，直到找到一个未被使用的花的种类 $c$，将 $c$ 标记为 $x$ 花园中种植的花的种类，然后继续枚举下一个花园。

枚举结束后，返回答案即可。

时间复杂度 $O(n+m)$，空间复杂度 $O(n+m)$。其中 $n$ 和 $m$ 分别是花园的数量和路径的数量。

func gardenNoAdj(n int, paths [][]int) []int {
	g := make([][]int, n)
	for _, p := range paths {
		x, y := p[0]-1, p[1]-1
		g[x] = append(g[x], y)
		g[y] = append(g[y], x)
	}
	ans := make([]int, n)
	for x := 0; x < n; x++ {
		used := [5]bool{}
		for _, y := range g[x] {
			used[ans[y]] = true
		}
		for c := 1; c < 5; c++ {
			if !used[c] {
				ans[x] = c
				break
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1059. 从起点到终点的所有路径 🔒

中等1 种解法

标签：图、拓扑排序、Kosaraju 算法、Tarjan 强连通分量算法

题目、示例与约束

给定有向图的边 edges，以及该图的起点 source 和目标终点 destination，确定从起点 source 出发的所有路径是否最终结束于目标终点 destination，即：

• 从起点 source 到目标终点 destination 存在至少一条路径
• 如果存在从起点 source 到没有出边的节点的路径，则该节点就是路径终点。
• 从起点source到目标终点 destination 可能路径数是有限数字

当从起点 source 出发的所有路径都可以到达目标终点 destination 时返回 true，否则返回 false。

 

示例 1：

输入：n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
输出：false
说明：节点 1 和节点 2 都可以到达，但也会卡在那里。

示例 2：

输入：n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3
输出：false
说明：有两种可能：在节点 3 处结束，或是在节点 1 和节点 2 之间无限循环。

示例 3：

输入：n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3
输出：true

 

提示：

• 1 <= n <= 104
• 0 <= edges.length <= 104
• edges[i].length == 2
• 0 <= ai, bi <= n - 1
• 0 <= source <= n - 1
• 0 <= destination <= n - 1
• 给定的图中可能带有自环和平行边。

方法一：DFS · Go 实现

思考

要确认从 $source$ 出发的每条路径都停在 $destination$ 且图中无环通向别处。 $n,m\le {10}^4$，应对每个点记忆「正在访问 / 已确认可达终点」，以免重复搜索。

终点若仍有出边则不能作为终止。DFS 遇状态 $1$ 为环；无出边则必须等于终点；否则先标 $1$ 再要求所有后继成功，最后标 $2$。

从 $source$ 出发的搜索结果即为答案。

我们用一个状态数组 $\mathit{\text{state}}$ 来记录每个节点的状态，其中：

• 状态 0 表示该节点未被访问过；
• 状态 1 表示该节点正在被访问；
• 状态 2 表示该节点已经被访问过且可以通向终点。

我们首先将图构建为邻接表的形式，然后从起点出发进行深度优先搜索（DFS）。在 DFS 过程中：

• 如果当前节点的状态为 1，说明我们遇到了一个环，直接返回 $\text{false}$；
• 如果当前节点的状态为 2，说明该节点已经被访问过且可以通向终点，直接返回 $\text{true}$；
• 如果当前节点没有出边，则检查该节点是否为终点，如果是则返回 $\text{true}$，否则返回 $\text{false}$；
• 否则，将当前节点的状态设为 1，递归访问所有相邻节点；
• 如果所有相邻节点都能通向终点，则将当前节点的状态设为 2 并返回 $\text{true}$，否则返回 $\text{false}$。

答案为 $\text{dfs}(\text{source})$ 的结果。

时间复杂度 $O(n+m)$，其中 $n$ 和 $m$ 分别为节点数和边数。空间复杂度 $O(n+m)$，用于存储图的邻接表和状态数组。

func leadsToDestination(n int, edges [][]int, source int, destination int) bool {
	g := make([][]int, n)
	for _, e := range edges {
		g[e[0]] = append(g[e[0]], e[1])
	}
	if len(g[destination]) > 0 {
		return false
	}

	st := make([]int, n)

	var dfs func(i int) bool
	dfs = func(i int) bool {
		if st[i] != 0 {
			return st[i] == 2
		}
		if len(g[i]) == 0 {
			return i == destination
		}
		st[i] = 1
		for _, j := range g[i] {
			if !dfs(j) {
				return false
			}
		}
		st[i] = 2
		return true
	}

	return dfs(source)
}

力扣原题 · Doocs 题解来源

1129. 颜色交替的最短路径

中等1 种解法

标签：广度优先搜索、图

题目、示例与约束

给定一个整数 n，即有向图中的节点数，其中节点标记为 0 到 n - 1。图中的每条边为红色或者蓝色，并且可能存在自环或平行边。

给定两个数组 redEdges 和 blueEdges，其中：

• redEdges[i] = [ai, bi] 表示图中存在一条从节点 ai 到节点 bi 的红色有向边，
• blueEdges[j] = [uj, vj] 表示图中存在一条从节点 uj 到节点 vj 的蓝色有向边。

返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。

 

示例 1：

输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
输出：[0,1,-1]

示例 2：

输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
输出：[0,1,-1]

 

提示：

• 1 <= n <= 100
• 0 <= redEdges.length, blueEdges.length <= 400
• redEdges[i].length == blueEdges[j].length == 2
• 0 <= ai, bi, uj, vj < n

方法一：BFS · Go 实现

思考

边有红蓝两种颜色，相邻边必须异色，同一结点可能因到达颜色不同而需要分别访问。把状态定为 $(\mathit{\text{结点}},\mathit{\text{上一条边颜色}})$，从 $0$ 分别以红、蓝虚边出发做 BFS，首次到达某结点的层数即最短路。

按颜色分存邻接表，扩展时翻转颜色，避免走同色边。

题目实际上是最短路问题，我们可以考虑使用 BFS 来解决。

首先，我们对所有的边进行预处理，将所有的边按照颜色分类，存储到多维数组 $g$ 中。其中 $g[0]$ 存储所有红色边，而 $g[1]$ 存储所有蓝色边。

接着，我们定义以下数据结构或变量：

• 队列 $q$：用来存储当前搜索到的节点，以及当前边的颜色；
• 集合 $vis$：用来存储已经搜索过的节点，以及当前边的颜色；
• 变量 $d$：用来表示当前搜索的层数，即当前搜索到的节点到起点的距离；
• 数组 $ans$：用来存储每个节点到起点的最短距离。初始时，我们将 $ans$ 数组中的所有元素初始化为 $-1$，表示所有节点到起点的距离都未知。

我们首先将起点 $0$ 和起点边的颜色 $0$ 或 $1$ 入队，表示从起点出发，且当前是红色或蓝色边。

接下来，我们开始进行 BFS 搜索。我们每次从队列中取出一个节点 $(i,c)$，如果当前节点的答案还未更新，则将当前节点的答案更新为当前层数 $d$，即 $ans[i]=d$。然后，我们将当前边的颜色 $c$ 取反，即如果当前边为红色，则将其变为蓝色，反之亦然。我们取出颜色对应的所有边，如果边的另一端节点 $j$ 未被搜索过，则将其入队。

搜索结束后，返回答案数组即可。

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

func shortestAlternatingPaths(n int, redEdges [][]int, blueEdges [][]int) []int {
	g := [2][][]int{}
	for i := range g {
		g[i] = make([][]int, n)
	}
	for _, e := range redEdges {
		g[0][e[0]] = append(g[0][e[0]], e[1])
	}
	for _, e := range blueEdges {
		g[1][e[0]] = append(g[1][e[0]], e[1])
	}
	type pair struct{ i, c int }
	q := []pair{pair{0, 0}, pair{0, 1}}
	ans := make([]int, n)
	vis := make([][2]bool, n)
	for i := range ans {
		ans[i] = -1
	}
	d := 0
	for len(q) > 0 {
		for k := len(q); k > 0; k-- {
			p := q[0]
			q = q[1:]
			i, c := p.i, p.c
			if ans[i] == -1 {
				ans[i] = d
			}
			vis[i][c] = true
			c ^= 1
			for _, j := range g[c][i] {
				if !vis[j][c] {
					q = append(q, pair{j, c})
				}
			}
		}
		d++
	}
	return ans
}

力扣原题 · Doocs 题解来源

1136. 并行课程 🔒

中等1 种解法

标签：图、拓扑排序、有向无环图

题目、示例与约束

给你一个整数 n ，表示编号从 1 到 n 的 n 门课程。另给你一个数组 relations ，其中 relations[i] = [prevCoursei, nextCoursei] ，表示课程 prevCoursei 和课程 nextCoursei 之间存在先修关系：课程 prevCoursei 必须在 nextCoursei 之前修读完成。

在一个学期内，你可以学习 任意数量 的课程，但前提是你已经在 上 一学期修读完待学习课程的所有先修课程。

请你返回学完全部课程所需的 最少 学期数。如果没有办法做到学完全部这些课程的话，就返回 -1。

 

 

示例 1：

输入：n = 3, relations = [[1,3],[2,3]]
输出：2
解释：上图表示课程之间的关系图：
在第一学期，可以修读课程 1 和 2 。
在第二学期，可以修读课程 3 。

示例 2：

输入：n = 3, relations = [[1,2],[2,3],[3,1]]
输出：-1
解释：没有课程可以学习，因为它们互为先修课程。

 

提示：

• 1 <= n <= 5000
• 1 <= relations.length <= 5000
• relations[i].length == 2
• 1 <= prevCoursei, nextCoursei <= n
• prevCoursei != nextCoursei
• 所有 [prevCoursei, nextCoursei] 互不相同

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

思考

学期数是有向图中最长的先修链，且同一学期只能修当前入度为 $0$ 的课。按层做拓扑排序：每层同时修完队列中的课，层数即学期数。若结束后仍有课未修，则存在环，返回 $-1$。

我们可以先将课程之间的先修关系建立图 $g$，并统计每个课程的入度 $indeg$。

然后我们将入度为 $0$ 的课程入队，然后开始进行拓扑排序。每次从队列中取出一个课程，将其出队，并将其出度的课程的入度减 $1$，如果减 $1$ 后入度为 $0$，则将该课程入队。当队列为空时，如果还有课程没有修完，则说明无法修完所有课程，返回 $-1$。否则返回修完所有课程所需的学期数。

时间复杂度 $O(n+m)$，空间复杂度 $O(n+m)$。其中 $n$ 和 $m$ 分别为课程数和先修关系数。

func minimumSemesters(n int, relations [][]int) (ans int) {
	g := make([][]int, n)
	indeg := make([]int, n)
	for _, r := range relations {
		prev, nxt := r[0]-1, r[1]-1
		g[prev] = append(g[prev], nxt)
		indeg[nxt]++
	}
	q := []int{}
	for i, v := range indeg {
		if v == 0 {
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		ans++
		for k := len(q); k > 0; k-- {
			i := q[0]
			q = q[1:]
			n--
			for _, j := range g[i] {
				indeg[j]--
				if indeg[j] == 0 {
					q = append(q, j)
				}
			}
		}
	}
	if n == 0 {
		return
	}
	return -1
}

力扣原题 · Doocs 题解来源

1153. 字符串转化 🔒

困难1 种解法

标签：图、哈希表、字符串

题目、示例与约束

给出两个长度相同的字符串 str1 和 str2。请你帮忙判断字符串 str1 能不能在 零次 或 多次 转化 后变成字符串 str2。

每一次转化时，你可以将 str1 中出现的 所有 相同字母变成其他 任何 小写英文字母。

只有在字符串 str1 能够通过上述方式顺利转化为字符串 str2 时才能返回 true 。​​

 

示例 1：

输入：str1 = "aabcc", str2 = "ccdee"
输出：true
解释：将 'c' 变成 'e'，然后把 'b' 变成 'd'，接着再把 'a' 变成 'c'。注意，转化的顺序也很重要。

示例 2：

输入：str1 = "leetcode", str2 = "codeleet"
输出：false
解释：我们没有办法能够把 str1 转化为 str2。

 

提示：

• 1 <= str1.length == str2.length <= 104
• str1 和 str2 中都只会出现小写英文字母

方法一：哈希表 · Go 实现

思考

每次把某字符的全部出现改成另一字符，映射必须是函数：同一源字符不能指向两个目标。若 str1=str2 则已完成。

否则还须有空闲字符作「临时桶」，否则成环时无处中转；str2 用满 $26$ 个字母即无空闲，无法转换。哈希表记录并校验映射即可。

我们可以先判断 str1 和 str2 是否相等，若相等，直接返回 true。

然后我们统计 str2 中每个字母出现的次数，若出现的次数等于 $26$，说明 str2 包含了所有的小写字母，那么无论 str1 如何转换，都无法得到 str2，直接返回 false。

否则，我们用数组或哈希表 d 记录 str1 中每个字母转换后的字母。遍历字符串 str1 和 str2，若 str1 中的某个字母已经转换过，那么其转换后的字母必须与 str2 中对应位置的字母相同，否则返回 false。

遍历结束后，返回 true。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为字符串 str1 的长度，而 $C$ 为字符集大小，本题中 $C=26$。

func canConvert(str1 string, str2 string) bool {
	if str1 == str2 {
		return true
	}
	s := map[rune]bool{}
	for _, c := range str2 {
		s[c] = true
		if len(s) == 26 {
			return false
		}
	}
	d := [26]int{}
	for i, c := range str1 {
		a, b := int(c-'a'), int(str2[i]-'a')
		if d[a] == 0 {
			d[a] = b + 1
		} else if d[a] != b+1 {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

1192. 查找集群内的关键连接

困难1 种解法

标签：深度优先搜索、图、桥、双连通分量

题目、示例与约束

力扣数据中心有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号。它们之间以 服务器到服务器 的形式相互连接组成了一个内部集群，连接是无向的。用  connections 表示集群网络，connections[i] = [a, b] 表示服务器 a 和 b 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。

关键连接 是在该集群中的重要连接，假如我们将它移除，便会导致某些服务器无法访问其他服务器。

请你以任意顺序返回该集群内的所有 关键连接 。

 

示例 1：

输入：n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
输出：[[1,3]]
解释：[[3,1]] 也是正确的。

示例 2:

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

 

提示：

• 2 <= n <= 105
• n - 1 <= connections.length <= 105
• 0 <= ai, bi <= n - 1
• ai != bi
• 不存在重复的连接

方法一：Tarjan 算法 · Go 实现

思考

关键连接即桥：删除后连通分量增加。对每条边判断连通性若用并查集或 BFS，边数大时达不到要求。Tarjan 在一次 DFS 中维护发现序 $dfn$ 与最早返祖 $low$，树边满足 $low[v]>dfn[u]$ 时即为桥。无向图需跳过父边，避免把树边误当返祖。

此题中的「关键连接」即为「桥」。

「桥」：在一连通的无向图中，若去除某一边后会使得图不再连通，则这条边可以视作「桥」。

与之相应的概念还有「割点」。

「割点」：在一连通的无向图中，若去除某一点及所有与其相连的边后会使得图不再连通，则这个点可以视作「割点」。

用于求图中的「桥」与「割点」有一算法：tarjan 算法，这个算法使用先递归的访问相邻节点后访问节点自身的 dfs 方法，通过记录「访问的顺序：DFN」以及在递归结束后访问节点自身时探索其可以回溯到的最早被访问的节点来更新「最早可回溯的节点：low」，可以实现在 $O(n)$ 时间内找到图的「桥」与「割点」。同时，此种算法可以用于查找有向图中的强连通分量。

func criticalConnections(n int, connections [][]int) (ans [][]int) {
	now := 0
	g := make([][]int, n)
	dfn := make([]int, n)
	low := make([]int, n)
	for _, e := range connections {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	var tarjan func(int, int)
	tarjan = func(a, fa int) {
		now++
		dfn[a], low[a] = now, now
		for _, b := range g[a] {
			if b == fa {
				continue
			}
			if dfn[b] == 0 {
				tarjan(b, a)
				low[a] = min(low[a], low[b])
				if low[b] > dfn[a] {
					ans = append(ans, []int{a, b})
				}
			} else {
				low[a] = min(low[a], dfn[b])
			}
		}
	}
	tarjan(0, -1)
	return
}

力扣原题 · Doocs 题解来源

1203. 项目管理

困难1 种解法

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

题目、示例与约束

有 n 个项目，每个项目或者不属于任何小组，或者属于 m 个小组之一。group[i] 表示第 i 个项目所属的小组，如果第 i 个项目不属于任何小组，则 group[i] 等于 -1。项目和小组都是从零开始编号的。可能存在小组不负责任何项目，即没有任何项目属于这个小组。

请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：

• 同一小组的项目，排序后在列表中彼此相邻。
• 项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。

如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表 。

 

示例 1：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
输出：[6,3,4,1,5,2,0,7]

示例 2：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
输出：[]
解释：与示例 1 大致相同，但是在排序后的列表中，4 必须放在 6 的前面。

 

提示：

• 1 <= m <= n <= 3 * 104
• group.length == beforeItems.length == n
• -1 <= group[i] <= m - 1
• 0 <= beforeItems[i].length <= n - 1
• 0 <= beforeItems[i][j] <= n - 1
• i != beforeItems[i][j]
• beforeItems[i] 不含重复元素

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

思考

仅对项目做一次拓扑排序会打散同一小组，无法保证组内项目相邻。 $n\le 3\times {10}^4$，需要线性级的构图与排序。

约束分两层：组与组之间有先后，组内项目之间另有先后。无组项目可各成一组，使每个项目都属于某个组。组间边来自跨组依赖，组内边来自同组依赖。

为此先对组图拓扑，再按组序对组内项目拓扑。任一层出现环则无解。两层图把「组必须成块」与「项目先后」拆开，各做一次 Kahn 算法即可。

我们先遍历数组 $group$，对于每个项目，如果其不属于任何小组，则将其新建一个小组，编号为 $m$，并将 $m$ 的值加一。这样我们就能保证所有项目都属于某个小组了。然后，我们用一个数组 $groupItems$ 记录每个小组包含的项目，数组下标为小组编号，数组值为包含的项目列表。

接下来，我们需要建图。对于每个项目，我们需要建立两种图，一种是项目间的图，一种是小组间的图。我们遍历数组 $group$，对于当前项目 $i$，它所在的小组为 $group[i]$，我们遍历 $beforeItems[i]$，对于其中的每个项目 $j$，如果 $group[i]=group[j]$，说明 $i$ 和 $j$ 属于同一小组，我们在项目图中添加一条 $j\to i$ 的边，否则说明 $i$ 和 $j$ 属于不同的小组，我们在小组间的图中添加一条 $group[j]\to group[i]$ 的边，并且更新对应的入度数组。

接下来，我们先对小组间的图进行拓扑排序，得到排序后的小组列表 $groupOrder$，如果排序后的列表长度不等于小组总数，说明无法完成排序，返回空列表。否则，我们遍历 $groupOrder$，对于其中的每个小组 $gi$，我们将该小组包含的项目列表 $groupItems[gi]$ 进行拓扑排序，得到排序后的项目列表 $itemOrder$，如果排序后的列表长度不等于该小组包含的项目总数，说明无法完成排序，返回空列表。否则，我们将 $itemOrder$ 中的项目加入答案数组中，最终返回该答案数组即可。

时间复杂度 $O(n+m)$，空间复杂度 $O(n+m)$。其中 $n$ 和 $m$ 分别是项目总数和小组总数。

func sortItems(n int, m int, group []int, beforeItems [][]int) []int {
	idx := m
	groupItems := make([][]int, n+m)
	itemDegree := make([]int, n)
	groupDegree := make([]int, n+m)
	itemGraph := make([][]int, n)
	groupGraph := make([][]int, n+m)
	for i, g := range group {
		if g == -1 {
			group[i] = idx
			idx++
		}
		groupItems[group[i]] = append(groupItems[group[i]], i)
	}
	for i, gi := range group {
		for _, j := range beforeItems[i] {
			gj := group[j]
			if gi == gj {
				itemDegree[i]++
				itemGraph[j] = append(itemGraph[j], i)
			} else {
				groupDegree[gi]++
				groupGraph[gj] = append(groupGraph[gj], gi)
			}
		}
	}
	items := make([]int, n+m)
	for i := range items {
		items[i] = i
	}
	topoSort := func(degree []int, graph [][]int, items []int) []int {
		q := []int{}
		for _, i := range items {
			if degree[i] == 0 {
				q = append(q, i)
			}
		}
		ans := []int{}
		for len(q) > 0 {
			i := q[0]
			q = q[1:]
			ans = append(ans, i)
			for _, j := range graph[i] {
				degree[j]--
				if degree[j] == 0 {
					q = append(q, j)
				}
			}
		}
		return ans
	}
	groupOrder := topoSort(groupDegree, groupGraph, items)
	if len(groupOrder) != len(items) {
		return nil
	}
	ans := []int{}
	for _, gi := range groupOrder {
		items = groupItems[gi]
		itemOrder := topoSort(itemDegree, itemGraph, items)
		if len(items) != len(itemOrder) {
			return nil
		}
		ans = append(ans, itemOrder...)
	}
	return ans
}

力扣原题 · Doocs 题解来源