Here is the interview question prompt, presented for reference.

Given a directed graph represented via an adjacency list, write a class StronglyConnectedComponents with a count() method that would return the number of strongly connected components in a graph.

The definition of a strong connected component is a subgraph of a directed graph where there's a path in both directions between any two pair of vertices. In other words, in the following graph:

You'll notice there's paths for every pair:

A to B
A to C
B to C (through A)
B to A 
C to A (through B)
C to B 

The StronglyConnectedComponents method you define should be able to return 1 if presented the above graph.

Constraints

• Number of vertices in the graph <= 100000
• Number of edges in the graph <= 100000
• Let |V|, |E| represent the number of vertices and edges of the graph
• Expected time and space complexity : O(|V|*(|V|+|E|))
• Expected space complexity : O(|V|+|E|)

You can see the full challenge with visuals at this link.