[-] Q4
by ofird - Wednesday, 24 June 2009 11:18:57
I think i didn't understand the question or that it's wrong.
consider the next graph

z---->v<----u

i think that he is "had mesilati" if not  than why not?
else
lets look at the dfs run starting from z
d[z]= 0 f[z] =3
d[v]= 1 f[v]= 2
d[u] =4 f[u] =5 
so we get that (u,v) is a cross edge cause d[u]>f[v] and v was black.
what am i missing???
thread
Re: Q4
by golansha - Wednesday, 24 June 2009 12:03:04
The graph is indeed "had mesilati".
You ran DFS, while what is written is that we run DFS_visit. You run each DFS_visit without "remembering" the last DFS_visit you made. For your example:
 
DFS_visit from z:
d[z]= 0 f[z] =3
d[v]= 1 f[v]= 2
No crossing edges

DFS_visit from u:
d[u]= 0 f[u] =3
d[v]= 1 f[v]= 2
No crossing edges

DFS_visit from v:
d[v]= 0 f[v] =1
No crossing edges

thread