detect cycle的题。
1、用dfs做：
- 需要一个数据结构来储存当前走过的路径，每次走完这整条路成功的话，就应该把当前的路径走过与否改成false来返回，如果这条路失败，直接返回false
- 需要一个数据结构来储存总共走的路径，因为node间不一定全部有连接，而我们无需再检查已经走过的node
- 需要一个数据结构来储存当前节点之后是什么路径
class Solution {
private:
unordered_map<int, vector<int>> map;
bool dfs(int numCourses, int cur, vector<int>& curPath, vector<int>& totalPath, vector<int>& res)
{
if (curPath[cur]) return false; // detect cycle
if (totalPath[cur]) return true; // avoid duplicates
curPath[cur] = totalPath[cur] = 1; // explore a new node
for (int i: map[cur])
{
if (!dfs(numCourses, i, curPath, totalPath, res)) return false;
}
curPath[cur] = false; // undo current
res.push_back(cur); // record the valid current path
return true;
}
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites)
{
vector<int> curPath(numCourses);
vector<int> totalPath(numCourses);
vector<int> res;
for (auto &p: prerequisites) map[p.second].push_back(p.first); // make graph
for (int i = 0; i < numCourses; ++i) // in this form we won't lose information about unconnected vertexes
{
if (!totalPath[i] && !dfs(numCourses, i, curPath, totalPath, res)) return {};
}
reverse(res.begin(), res.end());
return res;
}
};
2、Kahn's algorithm
搞清楚Kahn's algorithm。这个算法的insight是，对于一个connected DAG来说，至少有一个node它的incoming edges是0。简单想一下，如果graph的头和尾是连起来的话，那么就没有incoming edges是0了。如果我们每一次都将incoming edges是0的node加入到一个array里面，比如1->2->3，第一次把1加入，这时候把它的outgoing edges都去掉，于是把2加入，再去掉edge，再把3加入，这样的话array数量是3==node数量，排列是123。对于1->2->3->2来说，当我们把1加入array并去掉edge的时候，会发现2还有incoming edge，所以不能加入array，这样一来整个图就没有incoming edge为0的node了，但我们并没有遍历整个图，所以说这个图是有圈圈的。
所以这个算法的步骤就是：将所有incoming edge为0的node加入到一个array中，每次加入时去除outgoing edges，这样不断循环，如果图中没有符合条件的node了，我们也已经遍历完了这个图，那么所得array就是拓扑排序的顺序。这个算法的base case是一个node的时候，incoming edge=0。其它更复杂的图通过处理都是想回到基于这个base case的判断上来。
至于说为什么所得array就是拓扑排序的顺序，因为每次我们都是将node的incoming edge是0是那个node加入到array，也就是把处于顺序优先的node先放进array了，那最后所得必然就是顺序了。
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites)
{
unordered_map<int, vector<int>> map_next;
queue<int> next;
vector<int> edges(numCourses);
vector<int> res;
for (auto &ele: prerequisites)
{
map_next[ele.second].push_back(ele.first);
edges[ele.first]++;
}
for (int i = 0; i < edges.size(); ++i)
{
if (!edges[i]) next.push(i);
}
while (!next.empty())
{
int top = next.front();
next.pop();
res.push_back(top);
for (auto num: map_next[top])
{
edges[num]--;
if (!edges[num]) next.push(num);
}
}
return res.size() == numCourses ? res : vector<int>();
}
};
在这个算法中，用stack, vector, queue，都可以得到正确的结果。
