$\begingroup$
$\endgroup$
2
I came across this theorem: enter image description here
It says: The first time we visit (u,v) , we do it in direction u to v, because entry[u] < entry[v], however this does not make sense to me. Consider this graph: enter image description here
The first time we try to use the edge (1/10,6/7), we try to do it from the 6/7 vertex to the 1/10 vertex, but clearly the entry time 6 is greater than entry time 1. Secondly, when do we ever explore an edge twice in DFS, all I know is that we do it once and then after v is done we backtrack.
-
$\begingroup$ I don't get the last sketch: what are the numbers before the / (slash), and what are the numbers after? Just parts of composite node labels? First one is the entry time? Whence? Any prior explanation what entry$(u)$ is? $\endgroup$greybeard– greybeard2025年11月07日 13:10:58 +00:00Commented Nov 7 at 13:10
-
$\begingroup$ cs.stackexchange.com/help/referencing $\endgroup$D.W.– D.W. ♦2025年11月10日 01:22:51 +00:00Commented Nov 10 at 1:22