MadeEasy Test Series 2015: Algorithms - Graph Algorithms

Question

Here i have option III is doubt.how option III always correct.one counter example is if i choose a tree where s is root node and v1& v2 are its child node then above question property i.e the vertices V1 and V2 that are simultaneously on the function call stack at some point during the execution of depth-first search from vertex s in a digraph is satisfies.but there is no any path from v1 to v2 or from v2 to v1.

Comments

yup must not be true but may be true .

---

Sir may be true means False na.so ans should be option a.but here option is c.

---

yes a will be ans

---

why is III not always true??....

---

there may be no path from V1 to V2

---

@srestha, i think it should be,

can you give a counter example in which both are not connected to each other and still both of them are in the stack...?

---

have u read the example given by sahu?

---

okk, i was confused with simultaneous ... if they will be connected then no meaning of simultaneous, hence option A is true...

---

the example given by @dileswar sahu is false as he has taken Tree but in question it mention directed GRAPH..hope it clear all your doubt

---

every tree is graph but graph need not tree.