AlgoDaily - How Many Strongly Connected

How Many Strongly Connected (Hard)

Good morning! Here's our prompt for today.

You may see this problem at Microsoft, Vmware, Zillow, Nvidia, Grammarly, Servicenow, Akamai, Tradeshift, and Proofpoint.

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:

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|)

xxxxxxxxxx
​
 
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);

OUTPUT

Results will appear here.