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

---

排课表问题，一看就是拓扑排序的题。
之前介绍过，拓扑排序有两种解法，一种是类似BFS的Kahn算法，另一种是DFS算法，具体可以参考维基百科的伪代码。
解法1：Kahn算法。基本思想，首先把所有入度为0的点放到集合S中（表示这些课没有先修课程，可以首先完成），然后不断从S中取点x，把x指向的所有的点y的边(x,y)删掉，如果删掉之后，y的入度也变为0了，把y也加入到S中。当S为空时，如果图中还有边没删掉，说明形成环了，否则是一个DAG。
想象一下图中的一个环，如同时有边(x,y)和(y,x)，则x和y因为都有入度，说明都不可能加入到集合S中，所以这两条边永远都删不掉。
Kahn的算法很好理解，代码类似于BFS，如下：

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int> >& prerequisites)
    {
        int numEdges = prerequisites.size();
        vector<set<int> > pre(numCourses, set<int>()), next(numCourses, set<int>());
        for (const auto& p : prerequisites) {
            pre[p.first].insert(p.second);
            next[p.second].insert(p.first);
        }
        queue<int> Q;
        for (int i = 0; i < numCourses; ++i) {
            if (pre[i].size() == 0)
                Q.push(i);
        }
        while (!Q.empty()) {
            int node = Q.front();
            Q.pop();
            for (const auto& n : next[node]) {
                pre[n].erase(node);
                –numEdges;
                if (pre[n].size() == 0)
                    Q.push(n);
            }
        }
        return numEdges == 0;
    }
};

本代码提交AC，用时15MS。
解法2：DFS算法。还可以用DFS求解，基本思想是，维护两个访问标记数组，visited[i]表示全局是否被访问数组，相当于维基百科中的permanently标记，onpath[i]表示当前DFS路径是否被访问数组，相当于维基百科中的temporarily标记。
对于所有visited[i]没访问的点i，我们DFS它。把从i开始DFS到的点标记为onpath[j]，如果在DFS的过程中访问到了onpath[k]被标记过的点，说明这条路形成了环，返回false，不是DAG。否则，如果visited[node]==1，说明node是DFS之前的点时被访问过，而之前的DFS返回了true，说明从node DFS的结果是不会形成环的，可以直接返回true。否则如果visited[node]==0，我们从node继续DFS，具体步骤是，首先标记onpath[node]=1，然后把node指向的所有点都DFS一遍，如果都没发现换，则永久标记visited[node]=1，说明从node这个点DFS是没问题的，不会形成环的；同时复位onpath[node]=0，以便下次DFS使用。
完整代码如下，实现方法完全参考维基百科中的DFS版本。

class Solution {
private:
    bool dfs(vector<int>& visited, vector<int>& onpath, vector<vector<int> >& graph, int node)
    {
        if (onpath[node] == 1)
            return false;
        if (visited[node] == 0) {
            onpath[node] = 1;
            for (int i = 0; i < graph.size(); ++i) {
                if (graph[node][i] == 1) {
                    if (!dfs(visited, onpath, graph, i))
                        return false;
                }
            }
            visited[node] = 1;
            onpath[node] = 0;
            return true;
        }
        return true;
    }

public:
    bool canFinish(int numCourses, vector<pair<int, int> >& prerequisites)
    {
        vector<vector<int> > graph(numCourses, vector<int>(numCourses, 0));
        for (const auto& p : prerequisites)
            graph[p.second][p.first] = 1;
        vector<int> visited(numCourses, 0), onpath(numCourses, 0); // visited==permanently; onpath=temporarily
        for (int i = 0; i < numCourses; ++i) {
            if (visited[i] == 0) {
                if (!dfs(visited, onpath, graph, i))
                    return false;
            }
        }
        return true;
    }
};

本代码提交AC，用时62MS，比Kahn慢好多。

二刷。上述解法也太复杂了，直接循环把入度为0的删掉就行了，完整代码如下：

class Solution {
public:
	bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
		vector<vector<int>> graph(numCourses, vector<int>(numCourses, 0));
		vector<int> indegree(numCourses, 0);
		for (int i = 0; i < prerequisites.size(); ++i) {
			graph[prerequisites[i][1]][prerequisites[i][0]] = 1;
			++indegree[prerequisites[i][0]];
		}
		int finish = 0;
		while (true) {
			bool found = false;
			for (int i = 0; i < numCourses; ++i) {
				if (indegree[i] == 0) {
					--indegree[i];
					++finish;
					found = true;
					for (int j = 0; j < numCourses; ++j) {
						if (graph[i][j] == 1) {
							graph[i][j] = 0;
							--indegree[j];
						}
					}
				}
			}
			if (!found)break;
		}
		return finish == numCourses;
	}
};

本代码提交AC，用时76MS。