10 7 Computing Strong Components The Algorithm 29 min

[@viharivemuri7202]

Dear professor, at 9:38 in the video you said, "We can construct G_rev,. an obvious optimization is to use the same Graph G but to go upwards in arcs". This is slightly confusing to me, When I represent a graph as an adjacency list, for a given vertex I only have access to vertices that are adjacent to this. How can we go upwards with this representation. When I implement SCC algorithm, I usually read the input edge list and construct both G and G_rev, is there a better way to do this?

[@victor.ezekiel]

Magical. The SCCs really just presented themselves.

[@ThePlacehole]

28:50, "you don't want to sort the nodes by their finishing times, because that would take n log n time." No, it wouldn't, the values are distinct.

[@adnanmohamed6517]

I don't get how "the values are distinct" is a justification for that sorting will not take O(n log n). Can you please explain?

[@viharivemuri7202]

"Values are distinct" is not the justification, the correct justfication is the values of finish times are between 1-n. So you can just use counting sort.@@adnanmohamed6517

[@sushmitanigam5787]

Why does it work

[@adnanmohamed6517]

Great question! Dr. Tim discusses this in the next video. @27:44 he says: "This is, of course, merely an example. You should not just take a single example as proof that this algorithm always works. I will give you a general argument in the next video."