DFS 环检测

• 邻接表建立图
• 递归遍历，vector<bool>记录路径
• 优化：visted<bool>数组存储已访问的节点，减少冗余计算(访问到已经访问的节点时，这个节点是否能形成环已经计算过了)
• 递归思路:
  • 已经成环，退出
  • 已经visited访问过，退出
  • 已经遍历过路径，说明有环，返回false
  • 没有，则遍历下一个路径，有false则退出返回false
  • 否则返回true

拓补排序

在判环的基础上，返回一条一次走完所有节点的顺序 即找到所有的图节点排成一行序列后，所有路径为单向的序列。 * 拓补排序 必要充分条件：有向无环图 * 那么有向无环图是什么，其实就是树 * 后序遍历反转，即拓补排序结果。