210. 课程表 II

中等图论拓扑排序（BFS / Kahn）力扣原题 ↗

题目描述

共有 numCourses 门课，编号 0 到 numCourses - 1。prerequisites[i] = [ai, bi] 表示上课程 ai 之前必须先上课程 bi。

给出一个能学完全部课程的上课顺序，用课程编号组成的数组返回。合法顺序可能不止一种，返回任意一种都可以。

如果无论如何都学不完所有课程，返回空数组。

示例 1

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

解释：课程 1 依赖课程 0，所以顺序为 [0,1]。

示例 2

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

解释：课程 1、2 都在课程 0 之后，课程 3 又在 1、2 之后。[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] 两两不同。

解题思路：拓扑排序（BFS / Kahn）

拓扑排序（Kahn 算法）。建边 b → a，统计每门课的入度（还有几门先修没修）。入度为 0 的课可以直接修，先放进队列。每次取出一门课加入答案，把它的后续课入度减 1，减到 0 就入队。最后如果修到的课少于 numCourses，说明有环。

为什么正确

队列里的课，它的所有先修都已经在 order 中；因此 order 始终是一个合法的前缀。

复杂度分析

时间 O(V + E)，空间 O(V + E)。

易错点

边的方向是 b → a（先修指向后续），入度加在 a 上，写反会得到反向的顺序。有环时要返回空数组，而不是修到一半的 order。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)
            indeg[a] += 1
        queue = collections.deque(i for i in range(numCourses) if indeg[i] == 0)
        order = []
        while queue:
            u = queue.popleft()
            order.append(u)
            for v in graph[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    queue.append(v)
        return order if len(order) == numCourses else []

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        int[] indeg = new int[numCourses];
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
            indeg[p[0]]++;
        }
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indeg[i] == 0) queue.offer(i);
        }
        int[] order = new int[numCourses];
        int k = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order[k++] = u;
            for (int v : graph.get(u)) {
                indeg[v]--;
                if (indeg[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        return k == numCourses ? order : new int[0];
    }
}

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indeg(numCourses, 0);
        for (auto& p : prerequisites) {
            graph[p[1]].push_back(p[0]);
            indeg[p[0]]++;
        }
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indeg[i] == 0) q.push(i);
        }
        vector<int> order;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            order.push_back(u);
            for (int v : graph[u]) {
                indeg[v]--;
                if (indeg[v] == 0) {
                    q.push(v);
                }
            }
        }
        return (int)order.size() == numCourses ? order : vector<int>();
    }
};

func findOrder(numCourses int, prerequisites [][]int) []int {
	graph := make([][]int, numCourses)
	indeg := make([]int, numCourses)
	for _, p := range prerequisites {
		graph[p[1]] = append(graph[p[1]], p[0])
		indeg[p[0]]++
	}
	queue := []int{}
	for i := 0; i < numCourses; i++ {
		if indeg[i] == 0 {
			queue = append(queue, i)
		}
	}
	order := []int{}
	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		order = append(order, u)
		for _, v := range graph[u] {
			indeg[v]--
			if indeg[v] == 0 {
				queue = append(queue, v)
			}
		}
	}
	if len(order) == numCourses {
		return order
	}
	return []int{}
}

var findOrder = function(numCourses, prerequisites) {
    const graph = Array.from({ length: numCourses }, () => []);
    const indeg = new Array(numCourses).fill(0);
    for (const [a, b] of prerequisites) {
        graph[b].push(a);
        indeg[a]++;
    }
    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indeg[i] === 0) queue.push(i);
    }
    const order = [];
    let head = 0;
    while (head < queue.length) {
        const u = queue[head++];
        order.push(u);
        for (const v of graph[u]) {
            indeg[v]--;
            if (indeg[v] === 0) {
                queue.push(v);
            }
        }
    }
    return order.length === numCourses ? order : [];
};

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
    const graph = Array.from({ length: numCourses }, (): number[] => []);
    const indeg = new Array(numCourses).fill(0);
    for (const [a, b] of prerequisites) {
        graph[b].push(a);
        indeg[a]++;
    }
    const queue: number[] = [];
    for (let i = 0; i < numCourses; i++) {
        if (indeg[i] === 0) queue.push(i);
    }
    const order: number[] = [];
    let head = 0;
    while (head < queue.length) {
        const u = queue[head++];
        order.push(u);
        for (const v of graph[u]) {
            indeg[v]--;
            if (indeg[v] === 0) {
                queue.push(v);
            }
        }
    }
    return order.length === numCourses ? order : [];
}

载入编辑器，自己跑一遍 →

其他解法

Kahn 算法按“先修先出”的顺序从前往后构造序列；DFS 按“最后修的最先完成”从后往前构造，最后反转。两者都能顺便判断是否有环，得到的合法顺序可能不同。

解法 2：深度优先搜索（后序逆序）时间 O(n+m)，空间 O(n+m)

用三色标记做 DFS：进入结点时标 1，遇到状态为 1 的后继说明有环，直接返回空数组。一个结点的所有后继都处理完后标 2，并把它压入后序序列。此时依赖它的课程都已在序列中，所以后序序列反转后就是一个合法的修课顺序。

在判环的同时得到拓扑序，不需要入度数组。需要理解为什么要把后序反转；递归深度可达 n。

import sys
from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        sys.setrecursionlimit(max(10000, numCourses + 100))
        g = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            g[b].append(a)
        state = [0] * numCourses
        post = []

        def has_cycle(u):
            state[u] = 1
            for v in g[u]:
                if state[v] == 1 or (state[v] == 0 and has_cycle(v)):
                    return True
            state[u] = 2
            post.append(u)
            return False

        for i in range(numCourses):
            if state[i] == 0 and has_cycle(i):
                return []
        return post[::-1]

class Solution {
    private List<List<Integer>> g;
    private int[] state;
    private int[] order;
    private int k;

    private boolean hasCycle(int u) {
        state[u] = 1;
        for (int v : g.get(u)) {
            if (state[v] == 1 || (state[v] == 0 && hasCycle(v))) return true;
        }
        state[u] = 2;
        order[k--] = u;
        return false;
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        g = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) g.add(new ArrayList<>());
        for (int[] p : prerequisites) g.get(p[1]).add(p[0]);
        state = new int[numCourses];
        order = new int[numCourses];
        k = numCourses - 1;
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0 && hasCycle(i)) return new int[0];
        }
        return order;
    }
}

class Solution {
    vector<vector<int>> g;
    vector<int> state, post;

    bool hasCycle(int u) {
        state[u] = 1;
        for (int v : g[u]) {
            if (state[v] == 1 || (state[v] == 0 && hasCycle(v))) return true;
        }
        state[u] = 2;
        post.push_back(u);
        return false;
    }
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        g.assign(numCourses, {});
        state.assign(numCourses, 0);
        post.clear();
        for (auto& p : prerequisites) g[p[1]].push_back(p[0]);
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0 && hasCycle(i)) return {};
        }
        reverse(post.begin(), post.end());
        return post;
    }
};

func findOrder(numCourses int, prerequisites [][]int) []int {
	g := make([][]int, numCourses)
	for _, p := range prerequisites {
		g[p[1]] = append(g[p[1]], p[0])
	}
	state := make([]int, numCourses)
	post := []int{}
	var hasCycle func(u int) bool
	hasCycle = func(u int) bool {
		state[u] = 1
		for _, v := range g[u] {
			if state[v] == 1 || (state[v] == 0 && hasCycle(v)) {
				return true
			}
		}
		state[u] = 2
		post = append(post, u)
		return false
	}
	for i := 0; i < numCourses; i++ {
		if state[i] == 0 && hasCycle(i) {
			return []int{}
		}
	}
	for i, j := 0, len(post)-1; i < j; i, j = i+1, j-1 {
		post[i], post[j] = post[j], post[i]
	}
	return post
}

var findOrder = function(numCourses, prerequisites) {
    const g = Array.from({ length: numCourses }, () => []);
    for (const [a, b] of prerequisites) g[b].push(a);
    const state = new Array(numCourses).fill(0);
    const post = [];
    const hasCycle = (u) => {
        state[u] = 1;
        for (const v of g[u]) {
            if (state[v] === 1 || (state[v] === 0 && hasCycle(v))) return true;
        }
        state[u] = 2;
        post.push(u);
        return false;
    };
    for (let i = 0; i < numCourses; i++) {
        if (state[i] === 0 && hasCycle(i)) return [];
    }
    return post.reverse();
};

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
    const g: number[][] = Array.from({ length: numCourses }, () => []);
    for (const [a, b] of prerequisites) g[b].push(a);
    const state: number[] = new Array(numCourses).fill(0);
    const post: number[] = [];
    const hasCycle = (u: number): boolean => {
        state[u] = 1;
        for (const v of g[u]) {
            if (state[v] === 1 || (state[v] === 0 && hasCycle(v))) return true;
        }
        state[u] = 2;
        post.push(u);
        return false;
    };
    for (let i = 0; i < numCourses; i++) {
        if (state[i] === 0 && hasCycle(i)) return [];
    }
    return post.reverse();
};

图论专题的其他题目

查看图论全部题目 →