When I say $$Given $($di$)$graph G as input$,$ I mean we are given the adja$-$

cency lists for the $($di$)$graph$,$ i$.$e$.,$ Adj$[$v$]$ for every vertex v in the $($di$)$graph$.$

$*$ Recall that vertices are $1***$ n$.$ So$,$ you may use for each vertex v in

G or for v $=1$ to n$,$ whichever is appropriate when you want to process

each vertex.

$*$ Keep in mind that a complexity of O$($n$2)$ is not as good as O$($m $+$ n$).$

$*$ If you are going to compute any extra information, clearly state what

you are doing.

$*$ You must use the notation and style of pseudo$-$code as in the book $($or in

the notes for the class$).$

$(1)(10$ pts$)$ Recall that when we do a DFS on a digraph, we can encounter

two types of cross edges: one is between vertices in the same tree in the

DFS$-$forest, and the other is between vertices in different trees in the

DFS$-$forest. Present a complete O$($m $+$ n$)$ time algorithm that, given

a digraph G$,$ performs DFS$,$ and during the search detects all the

cross edges of each type and outputs them in the following format:

$4->3$ is a cross edge within a tree

$6->8$ is a cross edge across trees

Hint: You should already know, from class, how to detect a cross edge.

How do you tell one type from another? Here is one way: simply keep

track for each vertex w$,$ the root of the DFS$-$tree it belongs to; record

that information in the array entry root$[$w$]$ and use it$.*****$write pesucode to create an algorithm that determines all the cross edges in a dfs forest