Mark As Completed Discussion

Good afternoon! Here's our prompt for today.

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.

Description

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:

Description

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

SNIPPET
1A to B
2A to C
3B to C (through A)
4B to A 
5C to A (through B)
6C 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|)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Here's how we would solve this problem...

How do I use this guide?