In a directed graph G = (V, E), a vertex v is called middle if and only if for every vertex x in V either there exists a directed path from v to x, or there exists a directed path from x to v.

(a) Given a directed acyclic graph G and a vertex u in V, provide an O(|V |+|E|) time algorithm for determining whether or not vertex u is middle in G. (3 marks)

(b) (This part is optional, it may be completed for bonus marks) Given an acyclic directed graph G = (V, E) provide an O(|V | + |E|) time algorithm for computing all the middle vertices of G. (4 bonus marks)

(c) (When doing this part you may assume a solution to part (b) is available) Given a general directed graph G = (V, E) provide an O(|V | + |E|) time algorithm for computing all the middle vertices of G. (4 marks, for 2 marks provide a correct but slower algorithm)