Q$1.$ Imagine a graph depicting interconnected cities with edges representing their connections. In this

graph, some nodes are marked in red to denote cities affected by COVID$-19,$ while others remain

unmarked, signifying healthy cities. Your task is to determine the duration required for the COVID$-19$

virus to spread to all unaffected cities, given that it takes one unit of time to traverse between any two

cities.

$($a$)$ Explain clearly your algorithmic approach to solve the problem. $($explain your solution, like in

class$)[$BFS or DFS$?$ think about your solution, which one can be used$]$

$($b$)$ Write the pseudocode for your above solution.

Q$2.$ You are given an undirected graph $G=(V,E).$ Give an algorithm based on DFS that determines in

$O(|V|+|E|)$ time whether there is a cycle in the graph.

$($a$)$ Explain clearly your algorithmic approach to solve the problem. $($Think about corner cases, what

if you run DFS and there are nodes which are not visited$)$

$($b$)$ Write the pseudocode for your above solution.