Strongly Connected Components
3. Consider the un-weighted directed graph G = (V, E) below. c
(a) (6 points) Show the strongly connected components (SCC) of G. Give your answer as the lists of vertices that belong to the same SCC. Each vertex must belong to one and only one SCC. Your answer must have the minimum number of SCC. No justification needed.
(b) (6points) BuildthecomponentgraphGSCC =(VSCC,ESCC)ofG.Youcandrawitorgiveits set of vertices V SCC and edges ESCC. No justification needed.
Copyright By PowCoder代写 加微信 powcoder
COMP 251 – Midterm Page 7 of 10 Fall 2021
(c) (8 points) Describe an algorithm that computes the component graph. Your algorithm must be as efficient as possible.
(d) (6 points) Give the complexity of your algorithm. The complexity must be represented using an asymptotic notation (i.e. big O) and it must be a tight bound of the worst case running time of your proposed algorithm. No justification needed.
COMP 251 – Midterm Page 8 of 10 Fall 2021
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com