In a directed graph, the existence of a path from a vertex _u to a vertex _v does not imply the existence of a path from _v back to _u. As a result, finding a path from _u to _v does not necessarily mean that they are in the same component. Finding the components of a directed graph requires a more sophisticated approach than a pure depth-first search.

Deliverables:

GitHub Classroom: https://classroom.github.com/a/xR_lUIYN

Required Files: compile.sh, run.sh

Optional Files: *.py, *.java, *.clj, *.kt, *.js, *.sh

Part 1: Strongly Connected Components

Recall that a strongly connected component of a directed graph is a set of vertices within which there exists a

directed path between every pair of vertices. For example, consider the following directed graph:

This graph contains three strongly connected components: {_v1,v2,v3}, {_v0,v4}, and {_v5}. Further recall that such components are maximal, in that no more vertices may be added to a component without breaking its strong connectedness. Thus, _v0 alone does not form a component, because _v4 can still be added. In your programming language of choice per Assignment 1, implement an algorithm to find the strongly connected components of a directed graph. To help you get started, note the following observations:

• No strongly connected component can span multiple trees in a forest generated by a depth-first search.
• Assigning pre- and postvisit numbers to vertices during a depth-first

search allows identification of back edges. 2_,7

• Finding a back edge during a depth-first search indicates the existence ^v3 of a cycle.
• All vertices along a cycle must be in the same strongly connected _3,6

component. v₁

• If two cycles share any vertices, then they are both in the same strongly

connected component. _4,5

v₅

Each input graph will be provided as an edge list: each edge in the graph will be represented by a commaseparated pair of vertex identifiers, indicating an edge from the first vertex to the second.

You may assume that vertex identifiers are contiguous natural numbers they begin at ₀, and there will be no gaps in the identifiers used. You may also assume that the graph will be simple and will not contain any isolated vertices.

For example, the above graph could be represented as:

0, ^[1]0, 3 2, 3 0, 4 1, 5 4, 3

3, 1

1, 2

4, 0

Your program must accept as a command line argument the name of a file containing an edge list as described above, then print to stdout the strongly connected components according to the following format:

• Vertices within the same component appear on a single comma-separated line. Vertices in different components appear on different lines.
• Each lines vertices must be sorted in ascending order. Note that vertex identifiers are integers, not strings. The lines themselves must be sorted in ascending order using their smallest vertex identifiers. For example:

>$ ./compile.sh

>$ ./run.sh in1.txt

3 Strongly Connected Component(s):

0, 4

1, 2, 3

5

Your program will be tested using diff, so its printed output must match exactly.

[1] of 3