Building condensation

Report a typo

Given the directed graph below:

Condensed graph

The condensation of a directed graph GG, or condensed graph GG is a directed acyclic graph in which each node represents a strongly connected component in the original graph GG. For instance, if nodes 55, 77 and 88 form a strongly connected component in GG, this component will be represented as a single node 578578 in the condensed graph.

All edges of GG that do not belong to a strongly connected component remain unchanged in the condensed graph. For example, if the graph GG contains two strongly connected components and a directed edge from the first component (comprising of nodes nodes 11, 22, and 33) to the second (comprising of nodes 44, 55, 66, and 77), then the condensed graph will have two nodes 123123 and 45674567, with a directed edge from 123123 to 45674567. If two strongly connected components in a graph GG are connected by more than one edge, the resulting condensed graph will still have only one edge between the corresponding nodes.

Use Kosaraju's algorithm to identify the strongly connected components in the graph and construct its condensation. The expected output format is the following:

13 59
59 78

In the provided format, each line corresponds to an edge in the condensed graph. The digits represent the nodes within a strongly connected component, and these node labels are sorted in an ascending order.

Enter a short text
___

Create a free account to access the full topic