(i) Consider the directed graph 1 -> 2 -> 3 ->4 with 4 vertices and 3 arcs. Describe the result of running DFS on it, and discuss how the result depends on the order of vertices. (Recall that to make DFS deterministic, an order on the vertices is always assumed.) [4 marks]

(ii) Describe a linear-time algorithm deciding whether a graph (now undi- rected) is connected or not, and argue why it is linear time (for full marks there needs to be some explanation why the algorithm indeed runs in linear time).