[LeetCode 207] 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.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

click to show more hints.

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.
• 1. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
• 1. Topological sort could also be done via BFS.

Diffculty
Medium

Similar Problems
[LeetCode 210] Course Schedule II Medium [LeetCode 261] Graph Valid Tree Medium [LeetCode 310] Minimum Height Tree Medium

Analysis

题目等价为：检测有向图中是否有环

LeetCode 中关于图的题很少，有向图的仅此一道，还有一道关于无向图的题是 [Clone Graph][]，图这种数据结构相比于树，链表这些数据结构要更为复杂一些，尤其是有向图，比较麻烦。

（1） BFS 解法 我们定义二维数组 graph 来表示这个有向图，一维数组 in 来表示每个顶点的入度。 我们开始先根据输入来建立这个有向图，并将入度数组也初始化好。然后我们定义一个 queue 变量，将所有入度为 0 的点放入队列中，然后开始遍历队列，从 graph 里遍历其连接的点，每到达一个新节点，就将该新节点的入度减一，如果此时该节点入度为 0 ，就把其放入队列末尾。直到遍历完队列中所有的值，若此时还有节点的入度不为 0 ，则说明环存在，返回 false，反之则返回 true。

// in 表示每个顶点的入度
// 入度为 0 的课程表示没有先修课

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<vector<int> > graph(numCourses, vector<int>(0));
        vector<int> in(numCourses, 0);
        for (auto a : prerequisites) {
            graph[a.second].push_back(a.first); // 每一行是一个 prerequsite，这一行中存的就是依赖于 prerequsite 的课程。边的方向是由 prerequisite -> class
            ++in[a.first];
        }
        queue<int> q;
        for (int i = 0; i < numCourses; ++i) { // 把所有入度为 0 的顶点存入 queue 中，并且依次遍历他们的邻接点。
            if (in[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            int t = q.front();
            q.pop();
            for (auto a : graph[t]) {
                --in[a];
                if (in[a] == 0) q.push(a);
            }
        }
        for (int i = 0; i < numCourses; ++i) {  // 只要还有入度为 0 的点，就说明存在环。
            if (in[i] != 0) return false;
        }
        return true;
    }
};

（2） DFS 解法 还是用二维数组来建立，和 BFS 不同的是，我们像现在需要一个一维数组 visit[] 来记录访问状态 大体思路是，先建立好有向图，跟 BFS 一样，然后从第一个门课开始，找其可构成哪门课，暂时将当前课程标记为已访问，然后对新得到的课程调用 DFS 递归，直到出现新的课程已经访问过了，则返回 false ，没有冲突的话返回 true ，然后把标记为已访问的课程改为未访问。

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>(0));
        vector<int> visit(numCourses, 0);
        for (auto a : prerequisites) {
            graph[a.second].push_back(a.first);
        }
        for (int i = 0; i < numCourses; ++i) {
            if (!canFinishDFS(graph, visit, i)) return false;
        }
        return true;
    }
    bool canFinishDFS(vector<vector<int>> &graph, vector<int> &visit, int i) {
        if (visit[i] == -1) return false;
        if (visit[i] == 1) return true;
        visit[i] = -1;
        for (auto a : graph[i]) {
            if (!canFinishDFS(graph, visit, a)) return false;
        }
        visit[i] = 1;
        return true;
    }
};