We can use DFS on an undirected graph by considering itdirected
by making each undirected edge as two anti-parallel directed
edges. As we have seen in class, DFS produces a rooted tree.
(1) Given a rooted tree T subgraph of G, could it have been
produced by a DFS of G starting at the root.
(2) We want to answer the same for a tree T which is not
rooted,i.e. you can determine the root where the DFS starts.If
the complexity of (1) is C, give an algorithm of complexityn*C
where n is the number of nodes. Can you do better?