LeetCode Course Schedule

LeetCode 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:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

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

排课表问题,一看就是拓扑排序的题。

之前介绍过,拓扑排序有两种解法,一种是类似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慢好多。

One thought on “LeetCode Course Schedule

  1. Pingback: LeetCode Course Schedule II | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *