题目链接：Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Hints:

  1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. There are several ways to represent a graph. For example, the input prerequisites is a graph represented by a list of edges. Is this graph representation appropriate?
  3. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  4. Topological sort could also be done via BFS.

这道题的要求是课程安排：有n门课，编号0~n-1。有一些课程需要有先决条件，例如选修课程0你必须首先选修课程1，表示为[0, 1]。给出课程总数以及课程的先决条件，判断能否修完所有课程。

可以注意到课程的先决条件之间的关系，构成了有向图。而判断能否修完所有课程就是判断该有向图是否是一个拓扑序列或者判断该图是否有环。

  1. BFS(拓扑排序)

记录每个节点的入度，然后找入度为0的节点，直到找完所有节点。如果没有找到入度为0的节点（没有找完所有节点），说明有环，无法构成拓扑序列，直接返回false。

同时，在找到入度为0的节点后，需要删除其节点（可以将该节点入度标志位-1），同时将该节点的后继节点的入度均减1，说明该节点对应的课程已经修完了。

需要注意一个问题，由于存在重复的先决条件，因此在生成有向图和统计入度的时候，需要特殊处理或者分布进行。

时间复杂度：O(n2)

空间复杂度：O(n2)

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<unordered_set<int>> matrix(numCourses); // 邻接表
        
        for(int i = 0; i < prerequisites.size(); ++ i)
            matrix[prerequisites[i][1]].insert(prerequisites[i][0]);
        
        vector<int> d(numCourses, 0); // 入度
        for(int i = 0; i < numCourses; ++ i)
            for(auto it = matrix[i].begin(); it != matrix[i].end(); ++ it)
                ++ d[*it];
        
        for(int j = 0, i; j < numCourses; ++ j)
        {
            for(i = 0; i < numCourses && d[i] != 0; ++ i);
            
            if(i == numCourses)
                return false;
            
            d[i] = -1;
            for(auto it = matrix[i].begin(); it != matrix[i].end(); ++ it)
                -- d[*it];
        }
        
        return true;
    }
};

  1. DFS(找环)

可以通过深度优先搜索进行找环，如果找到环，说明无法构成拓扑序列，也就是无法修完所有课程。

时间复杂度：O(n2)

空间复杂度：O(n2)

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<unordered_set<int>> matrix(numCourses); // 邻接表
        for(int i = 0; i < prerequisites.size(); ++ i)
            matrix[prerequisites[i][1]].insert(prerequisites[i][0]);
        
        // 标记已经确认没有构成环的节点，可能有环：false；确认无环：true
        vector<bool> flag(numCourses, false);
        unordered_set<int> visited; // 深度优先搜索时标记已经访问过的节点
        for(int i = 0; i < numCourses; ++ i)
            if(!flag[i]) // 如果已经确认该节点没有构成环，无需再次进行深搜
                if(DFS(matrix, visited, i, flag)) // 深搜找环
                    return false;
        return true;
    }
private:
    bool DFS(vector<unordered_set<int>> &matrix, unordered_set<int> &visited, int b, vector<bool> &flag)
    {
        flag[b] = true;
        visited.insert(b);
        for(auto it = matrix[b].begin(); it != matrix[b].end(); ++ it)
            if(visited.find(*it) != visited.end() || DFS(matrix, visited, *it, flag))
                return true;
        visited.erase(b);
        return false;
    }
};