Quiz Question – Strongly Connected Components (SCC) – Kosaraju-Sharir’s algorithm

2022-010

Discovering the strongly connected components in a graph is an important task in many applications for real problems. Kosaraju-Sharir’s algorithm is one of the algorithms that produce these important components on graphs and uses the DFS (depth-first search) algorithm in some of its phases.

Consider the figures below, where Figure (a) is the original directed graph, and Figure (b) is the same graph in reverse order.

Using the Kosaraju-Sharir’s algorithm, analyze the statements about the Strongly Connected Components (SCC) extracted from the graph:

1. There are only the three SCC: 7,8 – 11,12,9,10 – 0,5,4,2,3

2. There are only the three SCC: 6,11,12,9,10 – 0,1,5,4,2,3 – 7,8

3. Single node is always a SCC, and in the graph, they are the nodes 1 and 6

4. There are five SCC: 1 – 7,8 – 11,12,9,10 – 6 – 0,5,4,2,3

Select the correct alternative:

$$

1. Only statements 1, 3, 4 are correct.
2. Only statement 3 is correct.
3. Only statements 2, 3, and 4 are correct.
4. Only statements 3 and 4 are correct.
5. None of the above.

Original idea by: Rubens de Castro Pereira