207. 课程表

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

题目描述

共有 numCourses 门课，编号为 0 到 numCourses - 1。

数组 prerequisites 描述先修关系：prerequisites[i] = [ai, bi] 表示想上课程 ai，得先学完课程 bi。比如 [0, 1] 的意思是课程 1 要排在课程 0 前面。

判断有没有办法学完所有课程。可以返回 true，不可以返回 false。

示例 1

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

解释：先学课程 0，再学课程 1，就能学完。

示例 2

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

解释：课程 0 和课程 1 互为先修，形成循环，无法学完。

数据范围

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
所有先修关系对两两不同。

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

用入度队列进行拓扑排序。

为什么正确

处理数等于课程数才表示无环。

复杂度分析

时间 O(n+m)，额外空间 O(n+m)。

易错点

注意边界条件并在回溯或弹出后恢复状态。

参考代码

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

from collections import deque
class Solution:
 def canFinish(self,n,p):
  g=[[] for _ in range(n)];d=[0]*n
  for a,b in p:g[b].append(a);d[a]+=1
  q=deque(i for i,x in enumerate(d) if not x);done=0
  while q:
   u=q.popleft();done+=1
   for v in g[u]:d[v]-=1; q.append(v) if d[v]==0 else None
  return done==n

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int n = numCourses;
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        int[] d = new int[n];
        for (int[] e : prerequisites) {
            g.get(e[1]).add(e[0]);
            d[e[0]]++;
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (d[i] == 0) q.add(i);
        int done = 0;
        while (!q.isEmpty()) {
            int u = q.poll(); done++;
            for (int v : g.get(u))
                if (--d[v] == 0) q.add(v);
        }
        return done == n;
    }
}

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        int n = numCourses;
        vector<vector<int>> g(n);
        vector<int> d(n);
        for (auto& e : prerequisites) {
            g[e[1]].push_back(e[0]);
            d[e[0]]++;
        }
        queue<int> q;
        for (int i = 0; i < n; i++) if (!d[i]) q.push(i);
        int done = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop(); done++;
            for (int v : g[u])
                if (--d[v] == 0) q.push(v);
        }
        return done == n;
    }
};

func canFinish(numCourses int, prerequisites [][]int) bool {
	n := numCourses
	g := make([][]int, n)
	d := make([]int, n)
	for _, e := range prerequisites {
		a, b := e[0], e[1]
		g[b] = append(g[b], a)
		d[a]++
	}
	q := []int{}
	for i, x := range d {
		if x == 0 {
			q = append(q, i)
		}
	}
	done := 0
	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		done++
		for _, v := range g[u] {
			d[v]--
			if d[v] == 0 {
				q = append(q, v)
			}
		}
	}
	return done == n
}

var canFinish = function(numCourses, prerequisites) {
    const n = numCourses;
    const g = Array.from({ length: n }, () => []), d = new Array(n).fill(0);
    for (const [a, b] of prerequisites) { g[b].push(a); d[a]++; }
    const q = [];
    for (let i = 0; i < n; i++) if (!d[i]) q.push(i);
    let done = 0, head = 0;
    while (head < q.length) {
        const u = q[head++]; done++;
        for (const v of g[u]) if (--d[v] === 0) q.push(v);
    }
    return done === n;
};

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
    const n = numCourses;
    const g: number[][] = Array.from({ length: n }, () => []), d: number[] = new Array(n).fill(0);
    for (const [a, b] of prerequisites) { g[b].push(a); d[a]++; }
    const q: number[] = [];
    for (let i = 0; i < n; i++) if (!d[i]) q.push(i);
    let done = 0, head = 0;
    while (head < q.length) {
        const u = q[head++]; done++;
        for (const v of g[u]) if (--d[v] === 0) q.push(v);
    }
    return done === n;
};

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

其他解法

Kahn 算法从入度为 0 的课程开始逐层剔除，剔不完就说明有环；DFS 沿路径深入，在路径上再次遇到已在路径上的结点就说明有环。两者复杂度相同。

解法 2：深度优先搜索（三色标记判环）时间 O(n+m)，空间 O(n+m)

给每个课程标三种状态：0 未访问、1 正在当前递归路径上、2 已完成。从每个未访问的结点出发做 DFS：进入时标 1，遍历所有后继，如果遇到状态为 1 的结点，说明沿路径回到了自己，存在环；所有后继处理完后标 2。只要发现环就无法修完所有课程。

直接对应“有向图判环”，不需要统计入度。递归深度可达 n，对大图有栈溢出风险。

import sys
from typing import List

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

        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
            return False

        return not any(state[i] == 0 and has_cycle(i) for i in range(numCourses))

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

    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;
        return false;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        g = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) g.add(new ArrayList<>());
        for (int[] e : prerequisites) g.get(e[1]).add(e[0]);
        state = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0 && hasCycle(i)) return false;
        }
        return true;
    }
}

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

    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;
        return false;
    }
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        g.assign(numCourses, {});
        state.assign(numCourses, 0);
        for (auto& e : prerequisites) g[e[1]].push_back(e[0]);
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0 && hasCycle(i)) return false;
        }
        return true;
    }
};

func canFinish(numCourses int, prerequisites [][]int) bool {
	g := make([][]int, numCourses)
	for _, e := range prerequisites {
		g[e[1]] = append(g[e[1]], e[0])
	}
	state := make([]int, numCourses)
	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
		return false
	}
	for i := 0; i < numCourses; i++ {
		if state[i] == 0 && hasCycle(i) {
			return false
		}
	}
	return true
}

var canFinish = 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 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;
        return false;
    };
    for (let i = 0; i < numCourses; i++) {
        if (state[i] === 0 && hasCycle(i)) return false;
    }
    return true;
};

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
    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 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;
        return false;
    };
    for (let i = 0; i < numCourses; i++) {
        if (state[i] === 0 && hasCycle(i)) return false;
    }
    return true;
};

图论专题的其他题目

查看图论全部题目 →