DFS · 有向图找环
给一个有向图,判断它是否含有环。
方法:DFS 给节点三种颜色——白(没访问)、灰(在当前递归栈上)、黑(已完成)。若 DFS 时遇到一条指向灰色节点的边(回边),就说明有环。
输入:第 1 行 V E(顶点数、边数,顶点编号 0..V-1);接下来 E 行每行 u v 表示有向边 u→v。
输出:YES(有环)或 NO。
例:3 3 / 0 1 / 1 2 / 2 0 → 输出 YES。
给一个有向图,判断它是否含有环。
方法:DFS 给节点三种颜色——白(没访问)、灰(在当前递归栈上)、黑(已完成)。若 DFS 时遇到一条指向灰色节点的边(回边),就说明有环。
输入:第 1 行 V E(顶点数、边数,顶点编号 0..V-1);接下来 E 行每行 u v 表示有向边 u→v。
输出:YES(有环)或 NO。
例:3 3 / 0 1 / 1 2 / 2 0 → 输出 YES。