2022-133

Regarding Strongly Connected Components (SCC), which of the following assertions are true:

i) Any SCC with two or more nodes has a cycle

ii) SCC's are only possible in undirected graphs

iii) Kosaraju-Sharir's algorithm for finding SCC's runs in linear time

1. Only i) and iii) are true
2. Only ii) and iii) are true
3. Only i) is true
4. Only ii) is true
5. None of the above

Original idea by: Júlio César Martins