Mark As Completed Discussion

Good morning! 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

We'll now take you through what you need to know.

How do I use this guide?

Access all course materials today

The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.

Returning members can login to stop seeing this.