22.5.2. Using DFS for Strongly Connected Components

Try these first

1. 1.

   What is a strongly connected component?

   Hint

   Think about connectivity in subgraphs.

2. 2.

   What does DFS stand for?

   Hint

   Focus on how we traverse through graphs.

3. 3.

   What defines a strongly connected component?

   • A subset of vertices that can reach each other
   • A subset of vertices that cannot reach each other

   Hint

   It’s about how vertices relate to each other.

4. 4.

   True or False: Only back edges in a directed graph can indicate the presence of a cycle.

   • True
   • False

   Hint

   Think of the direction of edges in cycles.

5. 5.

   Given a directed graph with certain edges, use DFS to identify and list all strongly connected components.

   Hint

   Pay special attention to back edges.

6. 6.

   Design an algorithm that employs DFS to count the number of strongly connected components in a graph.

   Hint

   One count for each new SCC discovered!