心之所向便是光

Leetcode 207.课程表

  • 2021-07-21
  • 作者 Ender
  • 4.24K 字
  • 次阅读

题目描述：

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

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

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

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

示例 1：

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

示例 2：

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

提示：

  • $1 <= numCourses <= 10^5$
  • $0 <= prerequisites.length <= 5000$
  • $prerequisites[i].length == 2$
  • $0 <= a_i, b_i < numCourses$
  • prerequisites[i] 中的所有课程对 互不相同

链接：

https://leetcode-cn.com/problems/course-schedule

题目分析

1.深度优先搜索

  这个题目其实就是要我们根据先修课程信息建立一个有向图，然后分析该图是否存在拓扑排序（也即有向无环图）。而寻找一个有向图是否有环可以使用深度优先搜索或者广度优先搜索的方法。
  首先使用深度优先搜索，我们可以使用一个 visited 数组来记录是否已经遍历过结点。如果一个结点的后置结点都已经遍历完成，则它在拓扑排序中可以出现在这些结点的前面，可以满足拓扑排序的要求的。而若一个结点的后置结点还未遍历，则需要进行搜索，保证这些结点都遍历后才能进行回溯，在搜索时需要将其标记为遍历中，如果某个后置结点的后置结点是遍历中，则说明构成了环，就不存在拓扑排序。因此对一个结点存在三种状态：未遍历、遍历中、已遍历。我们分别用 0、1、2 表示这三种状态。
  另外，题目中给出的边（也即先修课程对）是成对的，而我们每次搜索的时候是需要搜索一个结点的所有的后置结点（也即以其为起点的边），则我们将其使用邻接表的形式重新存储，便于遍历。
  由于题目只需要判断是否有拓扑排序，而不需要输出排序结果，所以我们仅仅使用 valid 来记录是否出现不合法情况（存在环）即可，不合法则可以直接退出返回 false，在遍历所有的结点之后如果没有出现不合法就返回 true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    vector<vector<int>> edges;
    vector<int> visited;
    bool valid = true;

    void DFS(int Course){
        visited[Course] = 1;
        for(int endpoint : edges[Course]){
            if(visited[endpoint] == 0){
                DFS(endpoint);
                if(!valid) return;
            }
            else if(visited[endpoint] == 1){
                valid = false;
                return;
            }
        }
        visited[Course] = 2;
    }

public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for(auto prerequisite : prerequisites){
            edges[prerequisite[1]].push_back(prerequisite[0]);
        }
        for(int Course = 0; Course < numCourses && valid; Course++){
            if(visited[Course] == 0){
                DFS(Course);
            }
        }
        return valid;
    }
};

  时间复杂度：$O(m+n)$，其中 $m、n$ 分别是课程数和先修课程的要求数（也即结点和边的数目）。我们对图进行了一次深度优先搜索，每个结点和边都遍历了一次。
  空间复杂度：$O(m+n)$，其中 $m、n$ 分别是课程数和先修课程的要求数（也即结点和边的数目）。我们采用邻接表的形式存储了结点和边的信息，大小为 $O(m+n)$，而递归的最大深度也即结点数目 $O(m)$。因此总的时间复杂度为 $O(m+n)$。

2.BFS

  图的广度优先遍历则是和深度优先搜索相反的过程，深度优先搜索是将没有后置结点的结点加入已遍历队列，广度优先搜索则是将没有前置结点的结点加入已遍历队列。我们维护一个队列，将没有入度（没有前置结点）的结点加入队列。每次从队列取出一个结点视为遍历该结点，删除其发出的所有边（也即后置结点的该门先修课程已经能够满足）。
  我们还是和前面一样将边信息转化为邻接表。并且使用一个 indeg 数组记录每个结点的入度。删除边的操作其实就是将其指向的结点入度减 1。然后入度为 0 的结点就可以加入到队列中。
  由于我们只需要保证所有的结点都能被遍历，则只需要维护一个遍历结点的数目，最后能够等于总的结点数目即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> edges(numCourses);
        vector<int> indeg(numCourses, 0);
        for(auto prerequisite : prerequisites){
            edges[prerequisite[1]].push_back(prerequisite[0]);
            indeg[prerequisite[0]]++;
        }
        queue<int> q;
        int visited = 0;
        for(int Course = 0; Course < numCourses; Course++){
            if(indeg[Course] == 0){
                q.push(Course);
            }
        }
        while(!q.empty()){
            int Course = q.front();
            visited++;
            q.pop();
            for(int endpoint : edges[Course]){
                --indeg[endpoint];
                if(indeg[endpoint] == 0){
                    q.push(endpoint);
                }
            }
        }
        return visited == numCourses;
    }
};

  时间复杂度：$O(m+n)$，其中 $m、n$ 分别是课程数和先修课程的要求数（也即结点和边的数目）。我们对图进行了一次广度优先搜索，每个结点和边都遍历了一次。
  空间复杂度：$O(m+n)$，其中 $m、n$ 分别是课程数和先修课程的要求数（也即结点和边的数目）。我们采用邻接表的形式存储了结点和边的信息，大小为 $O(m+n)$，而队列的最大长度也即结点数目 $O(m)$。因此总的时间复杂度为 $O(m+n)$。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
, , ,
最后编辑：2021-08-14