0 votes 0 votes If the DFS finishing time f[u] < f[v] for two vertices u and v in a directed graph G, and u and v are in the same DFS tree in the DFS forest, then u is an ancestor of v in the depth first tree ? True /False can anyone explain it ? Algorithms zeal algorithms graph-algorithm zeal2019 + – Prince Sindhiya asked Jan 2, 2019 edited Mar 6, 2019 by ajaysoni1924 Prince Sindhiya 827 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply MiNiPanda commented Jan 2, 2019 reply Follow Share What is the question? What we need to answer here? 0 votes 0 votes Prince Sindhiya commented Jan 2, 2019 reply Follow Share @minipandA See it now 0 votes 0 votes MiNiPanda commented Jan 2, 2019 reply Follow Share False..? 0 votes 0 votes Magma commented Jan 2, 2019 reply Follow Share U and V can be siblings right ?? therefore I think it's false 0 votes 0 votes Prince Sindhiya commented Jan 2, 2019 reply Follow Share yeah false i am not getting the question :( can u please explain it 0 votes 0 votes Naveen Kumar 3 commented Jan 2, 2019 reply Follow Share false ..v may be visited after backtracking 0 votes 0 votes MiNiPanda commented Jan 2, 2019 reply Follow Share @Prince Sindhiya f(u)<f(v) means v will be popped later than u. So there will be some cases: 1) u and v are siblings and their parent is x. t=1 dfs(x) : x on stack t=2 dfs(u) : u on stack now u is not connected to anything else. So it will be popped off at t=3 so f(u)=3 then backtrack to x and it will call dfs(v) so v will be pushed at t=4. Then popped at t=5 i.e. f(v)=5 In this way f(u)<f(v) But if x calls dfs(v) before dfs(u) then the opp. will happen. So this case doesn't always give f(u)<f(v) but sometimes give. 2) v is ancestor of u Then v comes before u in the directed graph. t=1 dfs(v) ...v is pushed on stack . It calls dfs(u) t=2 dfs(u) ...u is pushed on stack. t=3 u pops off t=4 v pops off So in this case f(v)>f(u) always But reverse can't happen (you may check). 0 votes 0 votes Prince Sindhiya commented Jan 2, 2019 reply Follow Share @Minipanda got it thnxx very much bro :) 0 votes 0 votes Please log in or register to add a comment.