class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
}
};
210. 课程表 II
现在你总共有 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 <= 20000 <= prerequisites.length <= numCourses * (numCourses - 1)prerequisites[i].length == 20 <= ai, bi < numCoursesai != bi[ai, bi] 互不相同原站题解
java 解法, 执行用时: 4 ms, 内存消耗: 43.8 MB, 提交时间: 2023-09-10 12:12:08
class Solution {
List<List<Integer>> edges;
int[] indeg;
public int[] findOrder(int numCourses, int[][] prerequisites) {
edges = new ArrayList<List<Integer>>();
for (int i = 0; i < numCourses; ++i) {
edges.add(new ArrayList<Integer>());
}
indeg = new int[numCourses];
for (int[] info : prerequisites) {
edges.get(info[1]).add(info[0]);
++indeg[info[0]];
}
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < numCourses; ++i) {
if (indeg[i] == 0) {
queue.offer(i);
}
}
int[] res = new int[numCourses];
int count = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
res[count] = u;
count++;
for (int v: edges.get(u)) {
--indeg[v];
if (indeg[v] == 0) {
queue.offer(v);
}
}
}
return count == numCourses ? res : new int[0];
}
}
javascript 解法, 执行用时: 64 ms, 内存消耗: 45.3 MB, 提交时间: 2023-09-10 12:04:53
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {number[]}
*/
var findOrder = function(numCourses, prerequisites) {
const inDegree = new Array(numCourses).fill(0); // 入度数组
const map = {}; // 邻接表
for (let i = 0; i < prerequisites.length; i++) {
inDegree[prerequisites[i][0]]++; // 求课的初始入度值
if (map[prerequisites[i][1]]) { // 当前课已经存在于邻接表
map[prerequisites[i][1]].push(prerequisites[i][0]); // 添加依赖它的后续课
} else { // 当前课不存在于邻接表
map[prerequisites[i][1]] = [prerequisites[i][0]];
}
}
const queue = [];
for (let i = 0; i < inDegree.length; i++) { // 所有入度为0的课入列
if (inDegree[i] == 0) queue.push(i);
}
const ans = [];
while (queue.length) {
const selected = queue.shift(); // 当前选的课，出列
ans.push(selected);
const toEnQueue = map[selected]; // 获取这门课对应的后续课
if (toEnQueue && toEnQueue.length) { // 确实有后续课
for (let i = 0; i < toEnQueue.length; i++) {
inDegree[toEnQueue[i]]--; // 依赖它的后续课的入度-1
if (inDegree[toEnQueue[i]] == 0) { // 如果因此减为0，入列
queue.push(toEnQueue[i]);
}
}
}
}
if ( ans.length != numCourses ) return [];
return ans;
};
php 解法, 执行用时: 24 ms, 内存消耗: 22.5 MB, 提交时间: 2023-09-10 11:50:34
class Solution {
/**
* @param Integer $numCourses
* @param Integer[][] $prerequisites
* @return Integer[]
*/
function findOrder($numCourses, $prerequisites) {
$edges = array_fill(0, $numCourses, []);
$indeg = array_fill(0, $numCourses, 0);
foreach ( $prerequisites as $info ) {
$edges[$info[1]][] = $info[0];
$indeg[$info[0]]++;
}
$q = [];
for ( $i = 0; $i < $numCourses; $i++ ) {
if ( $indeg[$i] == 0 ) $q[] = $i;
}
$ans = [];
while ( !empty($q) ) {
$u = array_shift($q);
$ans[]= $u;
foreach ( $edges[$u] as $v ) {
$indeg[$v]--;
if ( $indeg[$v] == 0 ) $q[] = $v;
}
}
if ( count($ans) != $numCourses )
$ans = [];
return $ans;
}
}
golang 解法, 执行用时: 8 ms, 内存消耗: 6 MB, 提交时间: 2022-11-22 10:54:27
func findOrder(numCourses int, prerequisites [][]int) []int {
var (
edges = make([][]int, numCourses)
indeg = make([]int, numCourses)
result []int
)
for _, info := range prerequisites {
edges[info[1]] = append(edges[info[1]], info[0])
indeg[info[0]]++
}
q := []int{}
for i := 0; i < numCourses; i++ {
if indeg[i] == 0 {
q = append(q, i)
}
}
for len(q) > 0 {
u := q[0]
q = q[1:]
result = append(result, u)
for _, v := range edges[u] {
indeg[v]--
if indeg[v] == 0 {
q = append(q, v)
}
}
}
if len(result) != numCourses {
return []int{}
}
return result
}
python3 解法, 执行用时: 56 ms, 内存消耗: 15.9 MB, 提交时间: 2022-11-22 10:54:00
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# 存储有向图
edges = collections.defaultdict(list)
# 存储每个节点的入度
indeg = [0] * numCourses
# 存储答案
result = list()
for info in prerequisites:
edges[info[1]].append(info[0])
indeg[info[0]] += 1
# 将所有入度为 0 的节点放入队列中
q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])
while q:
# 从队首取出一个节点
u = q.popleft()
# 放入答案中
result.append(u)
for v in edges[u]:
indeg[v] -= 1
# 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
if indeg[v] == 0:
q.append(v)
if len(result) != numCourses:
result = list()
return result
python3 解法, 执行用时: 48 ms, 内存消耗: 18 MB, 提交时间: 2022-11-22 10:53:40
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# 存储有向图
edges = collections.defaultdict(list)
# 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
visited = [0] * numCourses
# 用数组来模拟栈，下标 0 为栈底，n-1 为栈顶
result = list()
# 判断有向图中是否有环
valid = True
for info in prerequisites:
edges[info[1]].append(info[0])
def dfs(u: int):
nonlocal valid
# 将节点标记为「搜索中」
visited[u] = 1
# 搜索其相邻节点
# 只要发现有环，立刻停止搜索
for v in edges[u]:
# 如果「未搜索」那么搜索相邻节点
if visited[v] == 0:
dfs(v)
if not valid:
return
# 如果「搜索中」说明找到了环
elif visited[v] == 1:
valid = False
return
# 将节点标记为「已完成」
visited[u] = 2
# 将节点入栈
result.append(u)
# 每次挑选一个「未搜索」的节点，开始进行深度优先搜索
for i in range(numCourses):
if valid and not visited[i]:
dfs(i)
if not valid:
return list()
# 如果没有环，那么就有拓扑排序
# 注意下标 0 为栈底，因此需要将数组反序输出
return result[::-1]