Let G$=($V$,$E$)$ be a directed graph with n nodes and m edges. The following algorithm computes another graph based on the graph G$=($V$,$E$).$ The new graph is called Line Digraph and has symbol L$($G$).$

a$)$ How many nodes and how many edges $($in O$(..))$ does the graph L$($G$)$ have? Prove your answer

b$)$ What well$-$known algorithm is the Line Digraph algorithm similar to$?$ Explain why.

c$)$ What is the time complexity of the Line Digraph algorithm

Algorithm LineDigraph

Input: Digraph $G=(V,E)$

Output: Line Digraph $L(G)$ of $G$

Create a line digraph $L(G)$ with every edge of $G$ as a node

vlarr a random node of $G$

procedure GetLineGraph $,$ prev