207. 课程表

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]]

输出: true

解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:

输入: 2, [[1,0],[0,1]]

输出: false

解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

Solution1（DFS）:

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
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        if(numCourses <= 0) return true;
        vector<int> G[numCourses];
        int vis[numCourses] = {0};
        for(int i = 0; i < numCourses; i++) G[i].clear();
        for(int i = 0; i < prerequisites.size(); i++){
            G[prerequisites[i][1]].push_back(prerequisites[i][0]);
        }
        for(int i = 0; i < numCourses; i++){
            if(!vis[i]){
                if(!dfs(G,vis,i)) return false;
            }
        }
        return true;
    }
    bool dfs(vector<int> G[], int vis[],int j){
        vis[j] = 2;
        for(int i = 0; i < G[j].size(); i++){
            if(vis[G[j][i]] == 2) return false;
            if(!vis[G[j][i]]){
                if(!dfs(G,vis,G[j][i])) return false;
            }
            
        }
        vis[j] = 1;
        return true;
    }
   
};
思路:

把该题看做判断一个有向图是否有环的问题。
进而可以看做一个染色问题：

  • 如果该节点没有被访问过，则是白色（用0表示）。

  • 如果该节点正在访问，但是没有访问结束，则是灰色（用2表示）。

  • 如果该节点已经访问，则是黑色（用1表示）。

只有在DFS中维护颜色数组（我这里为vis数组）即可。

Solution2（拓扑排序）：

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
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        int inDegree[numCourses] = {0};
        vector<int> G[numCourses];
        for(int i = 0; i < prerequisites.size(); i++){
            G[prerequisites[i][1]].push_back(prerequisites[i][0]);
            inDegree[prerequisites[i][0]]++;
        }
        queue<int> q;
        int inqnum = 0;
        for(int i = 0; i < numCourses; i++){
            if(inDegree[i] == 0){
                q.push(i);
            }
        }
        while(q.size()){
            inqnum++;
            int f = q.front();q.pop();
            for(int i = 0; i < G[f].size(); i++){
                inDegree[G[f][i]]--;
                if(inDegree[G[f][i]] == 0){
                    q.push(G[f][i]);
                }
            }
        }
        return inqnum == numCourses;
    }
};
思路：

利用拓扑排序，每次将节点入度为零所在的边删去并更新边的另一端节点的入度信息，如果在多轮“删边”之后还有结点，说明有环。