(Solved): The transpose of a directed graph G=(V,E) is the graph GT=(V,ET) where ET= {(v,u)VV(u,v) ...

The transpose of a directed graph $$G=(V,E)$$ is the graph $$G^T=\left(V,E^T\right)$$ where $$E^T=$$ $$\{(v,u)?V\times V?(u,v)?E\}$$. Give an algorithm for computing $$G^T$$ from $$G$$ where the input $$G$$ is given as an adjacency list. Analyze the running time of your algorithm using Big-Oh notation. A universal sink of a directed graph $$G=(V,E)$$ is a vertex $$s?V$$ such that the in-degree of $$s$$ is $$?V??1$$ and the out-degree of $$s$$ is 0 . Give an algorithm to determine whether a directed graph $$G=(V,E)$$ contains a universal sink in time $$O(?V?)$$-time where the input graph $$G$$ is given as an adjacency matrix.