algo-aha

拓扑排序

方法一：bfs不断删除入度为0的点。见ctci p632

入度为0的节点先入队，然后出队时把它所有邻居的入度减1，并把新入度为0的节点入队。这就是bfs，因已按特定规则入队，可省略visited[]数组。

• https://leetcode.com/problems/course-schedule/
• https://leetcode.com/problems/alien-dictionary/

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
	// 拓扑排序：不断删除入度为0的点，其实就是bfs
	vector<vector<int>> graph(numCourses);
	vector<int> indegree(numCourses, 0);
	for (auto &edge : prerequisites) {
		graph[edge[1]].push_back(edge[0]);
		indegree[edge[0]]++;
	}
	queue<int> q;
	for (int i = 0; i < numCourses; i++) {
		if (indegree[i] == 0) q.push(i);
	}
	int count = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		count++;
		for (int to : graph[u]) {
			if (--indegree[to] == 0) q.push(to);
		}
	}
	return count == numCourses;
}

方法二：点的后序编号=>逆拓扑排序，即在访问完所有邻接点后、当前点进输出栈。可以从任意节点开始后序dfs，只要最外层循环把所有节点都跑一遍。