207 Course Schedule

题目

207 Course Schedule

题解

题目的要求是：给出课程之间的依赖关系，验证是否能够给出一个完全满足依赖关系的课程安排。当且仅当没有一个课程直接或间接地依赖于课程本身时，我们才能给出一个满足要求的课程安排。

若以课程为顶点，依赖关系为有向边，那么问题可以转化为验证输入图上是否存在环。根据定理“图上存在环当且仅当DFS图中存在回边”，问题进一步转变为验证DFS图中是否有回边。

若以prev和post分别标记进入顶点和离开顶点的时间，回边(u,v)有post[v]大于post[u]的独特性质，所以我们只需对输入图进行DFS，并记录每个顶点的prev和post，最后根据回边的独特性质对每一条边进行检查，即可求出答案

代码

class Solution {
public:
	bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
		map<int, vector<int>> graph;
		for (size_t i = 0; i < prerequisites.size(); i++) {
			int v1 = prerequisites[i].first;
			int v2 = prerequisites[i].second;
			graph[v1].push_back(v2);
		}

		vector<bool> visited(numCourses, false);
		vector<int> prev(numCourses, 0);
		vector<int> post(numCourses, 0);
		int clock = 0;
		for (size_t i = 0; i < numCourses; i++)
		{
			if (!visited[i]) {
				dfs(i, visited, graph, prev, post, clock);
			}
		}

		for (size_t i = 0; i < prerequisites.size(); i++)
		{
			int u = prerequisites[i].first;
			int v = prerequisites[i].second;
			if (post[u] < post[v]) {
				return false;
			}
		}

		return true;
	}

private:
	void dfs(int current, vector<bool>& visited, map<int, vector<int>>& graph,
		vector<int>& prev, vector<int>& post, int& clock) {
		visited[current] = true;
		prev[current] = clock;
		clock++;
		for (size_t i = 0; i < graph[current].size(); i++)
		{
			int next = graph[current][i];
			if (!visited[next]) {
				dfs(next, visited, graph, prev, post, clock);
			}
		}
		post[current] = clock;
		clock++;
	};
};