[LeetCode]Course Schedule II

还是拓扑排序的问题，什么是拓扑排序呢？拓扑排序是对节点进行排序使得序列中的每一条边都可以从后面的节点指向前面某一个节点。值得注意的是拓扑排序不是唯一的，比如：

就有A, B, C, D和A, C, B, D两种排序方法。
那么对于拓扑排序问题，首先是能不能排序，这就是Course Schedule的问题。那么当我们确定没有环，如何进行拓扑排序呢？本质上来讲拓扑排序后的顺序就是对图进行postorder遍历之后获得序列的逆序，postorder遍历会先方位当前节点的相邻节点，访问完所有相邻节点之后，在访问当前节点，这样的性质可以满足拓扑排序的要求，因为对于v->w来说，我们有这么几种情况：

• dfs(w)已经被call过，说明w已经被访问过，这说明有其他的path通过w，那么w肯定已经被收入postorder序列，v在其之后，那么逆序的话v一定在w之前，这满足拓扑排序的要求
• dfs(w)没有被call过，说明之前没有被访问过，那么w访问完相邻节点之后被收入postorder序列，之后v被收入，逆序的话v一定在w之前，这满足拓扑排序的要求
• call dfs(v)的时候dfs(w)还没有没有return，但是这在DAG（无环有向图）当中是不可能的

所以postorder的逆序就是我们要的拓扑排序结果。那么对于求得这个序列我们有dfs和bfds两种方法。

对于dfs来说，我们只需要按照postorder的顺序进行dfs之后逆序返回即可，代码如下：

	class Solution {
	public:
	vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
	unordered_map<int, vector<int>> g;
	for(auto& e : prerequisites)
	g[e.second].emplace_back(e.first);
	vector<int> order;
	vector<bool> marked(numCourses), onStack(numCourses);
	for(int i = 0; i < numCourses; ++i)
	if(!dfs(g, marked, onStack, order, i))
	return {};
	reverse(order.begin(), order.end());
	return order;
	}
	private:
	bool dfs(unordered_map<int, vector<int>>& g, vector<bool>& marked, vector<bool>& onStack, vector<int>& order, int curr)
	{
	//there is cirlce
	if(onStack[curr])
	return false;
	if(marked[curr])
	return true;
	marked[curr] = true;
	onStack[curr] = true;;
	bool isDAG = true;
	for(auto& next : g[curr])
	if(!dfs(g, marked, onStack, order, next))
	isDAG = false;
	order.emplace_back(curr);
	onStack[curr] = false;
	return isDAG;
	}
	};

view raw Course scheduleII.cpp hosted with ❤ by GitHub

bfs的做法稍有不同，我们从所有没有出度的节点开始访问，这些一定是postorder中最先收录的节点，所以对bfs的结果我们不需要逆序输出，那么访问之后，把所有指向这些节点的边删掉，我们有会有新的一批叶节点，我们不断重复直到收录所有节点为止，对于DAG来说，这个一定是可以成功的。如果有环的话，我们只需要检测图的大小和输出的大小是否一样，对于环来说，我们不可能收录环上的任何节点，因为删除任何非环上边之后，环上每一个节点出度不可能为0。代码如下：

	class Solution {
	public:
	vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
	if (numCourses < 1)return {};
	vector<vector<int>> graph(numCourses, vector<int>());
	vector<int> in(numCourses, 0), res;
	for (auto p : prerequisites)
	{
	graph[p.second].push_back(p.first);
	in[p.first]++;
	}
	queue<int> q;
	for (int i = 0; i < numCourses; ++i)
	{
	if (!in[i])q.push(i);
	}
	while(!q.empty())
	{
	int curr = q.front();
	q.pop();
	res.push_back(curr);
	for (int i : graph[curr])
	{
	in[i]--;
	if (!in[i])q.push(i);
	}
	}
	return res.size() == numCourses? res: vector<int>();
	}
	};

view raw Course scheduleII_2.cpp hosted with ❤ by GitHub