[LeetCode]Course Schedule

本质上就是能否topological sorting的问题，能拓扑排序的充要条件是图示DAG，也就是说没有环，我们只需要检测建的有没有环就行了，用dfs搜索如果碰到了栈上的元素就说明有环，值得注意的是图可能有多个component的要每个component都搜索到并且避免重复搜索，我们需要一个marked数组来记录，代码如下，时间复杂度O(V + E)，空间复杂度O(V + E)：

	class Solution {
	public:
	bool canFinish(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<bool> marked(numCourses), onStack(numCourses);
	for(int i = 0; i < numCourses; ++i)
	if(!isDAG(g, marked, onStack, i))
	return false;
	return true;
	}
	private:
	bool isDAG(unordered_map<int, vector<int>>& g, vector<bool>& marked, vector<bool>& onStack, int curr)
	{
	if(onStack[curr])
	return false;
	if(marked[curr])
	return true;
	onStack[curr] = true;
	marked[curr] = true;
	bool hasCycle = false;
	for(auto& next : g[curr])
	if(!isDAG(g, marked, onStack, next))
	hasCycle = true;
	onStack[curr] = false;
	return !hasCycle;
	}
	};

view raw Course schedule.cpp hosted with ❤ by GitHub

另一方面我们可以通过检测是否有SCC(strong connected components)来判断当前图是否有环。在有向图中，如果存在一系列节点，其中任意两个节点相互之间有path可以到达，那么这些节点组成一个SCC，在一个图中，可能存在多个SCC，如下图：

对于单个节点来说，自身肯定是SCC。那么对于两个和两个以上节点组成的SCC，存在环是其充要条件。首先如果有环，那么很显然环上的节点全部都是SCC；反过来的话，如果存在u，v，他们是SCC中的两个节点，那么存在从v到u的路径，并且存在从u到v的路径，这本身就形成了环。所以对于这一题，我们只需要寻找所建图是否存在size大于等于2的SCC，如果有，说明有环，不可以拓扑排序。
确定了这一点之后，我们就要考虑如何寻找SCC。我们可以使用Kosaraju's Algorithm，具体的步骤为：

1. 对图进行DFS，直到遍历完所有的节点。对于每一个节点，访问完所有相邻节点之后，把当前节点推入stack（Postorder）
2. 把原图的每一条边反过来
3. 按照stack pop出来的顺序，对于每一个节点v进行DFS，所有到达的节点就是v所在的SCC

要分析这个算法，我们首先要明确的是，如果我们把每一个SCC看做一个节点，那么所有SCC可以组成一个有向图，例如对于上图，我们可以等价为：

SCC图没有环，如果有环的话那么所有SCC节点就可以组成一个更大的SCC，这个我们的前提是矛盾的。所以第一步DFS就是相当于生成SCC图的拓扑序列，因为Postorder DFS得到序列的逆序，其实就是SCC图的拓扑排序（证明）。所有存在{ABH}的节点都比{CDE}的节点晚收录，以此类推。也就是说假设SCC1有边指向SCC2，那么SCC1里的节点都比SCC2的节点晚收录。值得注意的是，这个结论无论我们从哪个节点开始DFS都是成立的。这个顺序可以给我们带来一些好处，因为如果我们从{F}开始DFS，之后DFS {CDE}/{IJKL}, 最后访问{ABH}，那么每一个SCC之间都不会互相干扰，也就是说，我们每一次DFS得到的节点，就是当前SCC的全部节点，不会有其他SCC的节点。所以我们按照SCC图拓扑排序的逆序DFS，每一次DFS可以得到并且仅得到当前节点所在的SCC的所有节点。那么我们有两种选择，要不按照拓扑排序逆序DFS，要不把每一条边反过来，然后按照拓扑序列DFS。即使我们取反每一条边，SCC包括的节点是不会变的。这两种方法用哪一种都行，这里我们采取第二种。代码如下：

	class Solution {
	public:
	bool canFinish(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<bool> marked(numCourses);
	stack<int> seqs;
	for(int i = 0 ; i < numCourses; ++i)
	dfs(g, marked, seqs, i);
	//reverse graph
	unordered_map<int, vector<int>> reverseG;
	for(auto& e : prerequisites)
	reverseG[e.first].emplace_back(e.second);
	marked = vector<bool>(numCourses, false);
	while(seqs.size())
	{
	int i = seqs.top();
	seqs.pop();
	stack<int> scc;
	dfs(reverseG, marked, scc, i);
	//graph has strong components with size larger than 1, which means g has cycle
	if(scc.size() > 1)
	return false;
	}
	return true;
	}
	private:
	void dfs(unordered_map<int, vector<int>>& g, vector<bool>& marked, stack<int>& seqs, int curr)
	{
	if(marked[curr])
	return;
	marked[curr] = true;
	for(auto& next : g[curr])
	dfs(g, marked, seqs, next);
	seqs.push(curr);
	}
	};

view raw Course schedule2.cpp hosted with ❤ by GitHub

两次DFS，时间复杂度O(V + E)，空间复杂度O(V + E)。