(a) Devise an algorithm with O(A) running time that checks whether the graph is connected, and if it is connected, simultaneously constructs a path connecting any two nodes. Hint: Start at a node, mark its neighbors, and continue.
(b) Repeat part (a) for the case where we want to check strong connectedness. (c) Devise an algorithm with O(A) running time that checks whether there exists a cycle that contains two given nodes. (d) Repeat part
(c) for the case where the cycle is required to be forward.