Please verify that the error is present in the most recent revision before reporting.
Chapter number or note title: 6.2
Page number: 231
Error description: From the argument:
for an edge u->v, if (1) u.post < v.post, then the graph contains a cycle containing u->v
doesn't immediately follow that
we can determine whether a given directed graph is a dag.
What's missing is an argument that every cycle contains an edge satisfying (1).
Suggested fix (if any): I think this should work: for any cycle C, consider the vertex $v \in C$ with the smallest v.pre and let u be its predecessor in C. Then u->v satisfies (1).
Please verify that the error is present in the most recent revision before reporting.
Chapter number or note title: 6.2
Page number: 231
Error description: From the argument:
doesn't immediately follow that
What's missing is an argument that every cycle contains an edge satisfying (1).
Suggested fix (if any): I think this should work: for any cycle C, consider the vertex $v \in C$ with the smallest v.pre and let u be its predecessor in C. Then u->v satisfies (1).