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.

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:

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?

xxxxxxxxxx

    'PASSED: Instantiate a graph and add vertices. The number returned should be `1`.'

var assert = require('assert');

​

class StronglyConnectedComponents {

  constructor(graph) {

    const numOfVertices = graph.verticesCount;

    this.count = 0;

    return this;

  }

​

  count() {

    return this.count;

  }

}

​

class Graph {

  constructor() {

    this.adjacencyList = new Map();

    this.verticesCount = 0;

  }

​

  addVertex(nodeVal) {

    this.adjacencyList.set(nodeVal, []);

    this.verticesCount++;

  }

​

  addEdge(src, dest) {

    this.adjacencyList.get(src).push(dest);

    this.adjacencyList.get(dest).push(src);

    // push to both adjacency lists

Here's our guided, illustrated walk-through.

How do I use this guide?