LeetCode 207. Course Schedule

There are a total of numCourses  courses you have to take, labeled from 0 to numCourses-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?

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: 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.

Constraints:

• The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
• You may assume that there are no duplicate edges in the input prerequisites.
• 1 <= numCourses <= 10^5

解析：这是一个课程排序的问题，在选课时课程之间存在依赖关系，比如[0,1]表示如果要选择0，必须先学习1.所有课程这样就形成了有向图，判断有向图中是否存在环，如果存在环则没法完成课程选择。采用深度优先遍历的思想，采用二维数组来建立有向图，同时用visit数组来存放当前节点的状态，0表示未访问，1表示正在访问，2表示已经访问过了。然后从第一门课程开始，将其标记为正在访问中，然后依次取其依赖的课程，进行深度优先遍历，判断当前访问节点的状态，如果已经访问过了则返回，如果处理访问中，则说明dfs路径中检测出了环。这样挨个处理，处理完成后把当前节点标记为已经访问了。思路如下：

代码如下：

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        // states: 0 = unkonwn, 1 == visiting, 2 = visited
        vector<int> visit(numCourses, 0);
        for(auto & item : prerequisites)
            graph[item[1]].push_back(item[0]);
        for(int i =0; i < numCourses; i++)
        {
            if(dfs(graph, i, visit)) return false;
        }
        return true;
    }
    bool dfs(vector<vector<int>>& graph, int cur, vector<int>& visit)
    {
        if(visit[cur] == 1)
            return true;
        if(visit[cur] == 2)
            return false;
        visit[cur] = 1;
        for(auto & next : graph[cur])
            if(dfs(graph, next, visit) == true)
                return true;
        visit[cur] = 2;
        return false;
    }
};

参考：