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.

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