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

import unittest

​

​

class Test(unittest.TestCase):

    def test_1(self):

        assert Graph("AB BC CD DA AE FB DG".split()).num_components() == 4

        print(

            "PASSED: assert Graph('AB BC CD DA AE FB DG'.split()).num_components() == 4"

        )

​

​

if __name__ == "__main__":

    unittest.main(verbosity=2)

    print("Nice job, 1/1 tests passed!")

​

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

How do I use this guide?