The manner in which the "order" vector is traversed

#1

would it make a difference if the order vector is traversed in some other order? Since we are performing a reverse dfs on each and every node anyway, and the reverse_dfs() function is actually responsible for dfs on the reverse graph grr ,is it really necessary to traverse the order vector in an opposite manner as well?
I am actually confused because the significance of order vector is that if x is before y, an edge exists from y to x, but I cant see how this would have an impact on the implementation shown here

#2

also, please tell how is the color for {1,2,3}->2 ? and for {4,5,6}->3 initially, the color was set to 1 and then DFS would first be made on the node “1” so the color for SCC {1,2,3} should be 1 and then color was incremented, so color for {4,5,6} should be 2 according to me

#3

yes it will make difference
the significance of order vector is that if x is before y, an edge exists from y to x,

in this algorithm first you have to make a stack in which this type of ordering is present
then we take element one by one from stack and use dfs traversal

first we pop y form stack as it comes later in ordering(so at top of stack)
and call dfs to print all component connected to this in reverse graph ( this is the logic to print strongly connected component that if there is edge form y to x in orginal graph then it should also present in reverse graph )

if x is also connected to y then it is visited already
if not then a new dfs call will be made for x

so ordering is important

1 Like
#4

which example are you taking
if it is from video
please tell time span

#5

@asaurabh_26

It is the input sir gave to the program, the output is shown towards the very end of the video

#6

if you have written the same code
please share it so that i can check it by running

or you can use my code it is giving correct output

i hope this helps
if doubt is resolved don’t forgot to mark it as resolved :grinning:

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.