Kosaraju's Algorithm For Finding Sccs But Keep Track Of Edge Between Sccs?

I currently have a working implementation of Kosaraji's algorithm that, given a directed graph with no weights, will print the SCCs in a graph. I would like to adapt it so it will

Solution 1:

One thing can be done that, you can assign each node a component id. For your example, lets say,

[1, 3, 2] => component id 1
[7, 9, 8] => component id 2
[4, 5, 6] => component id 3

Then create another graph (SCC_GRAPH) using this component id. To generate this graph, you can traverse the original graph once and for each edge (u,v) if their component id is different then create an edge in SCC_GRAPH with component_id(u) -> component_id(v).

For this example,

1->21->3

Then for a given node, get the component id of this node. Then find number of node reachable in SCC_GRAPH starting from the component id of the given node.