# Todai Entrance Exam: Subject 2018 – Problem 3

**(1)** AEFDG

**(2) **BCAEFDG

**(3)** Real-world problem: Task scheduling. If there are many dependent tasks to do then topological sort will point out the order of tasks to be completed (reference).

**(4)** function DFS: Replace “print u” in function DFS2 for “s.push(u)”.

**(5)**

The above code block visited each node of the graph once (thanks to the code line “visited[v] != TRUE”) so the time complexity of this code block is .

As has values corresponding to nodes so the time complexity of this code block is .

Overall, the time complexity of the algorithm shown in Fig. 5 is .

**(6)** For each of , we can use breadth-first search to traverse the graph (a node can be visited once) starting from and have a list to store the values of the child nodes in last-in last-out fashion. We then concatenate these lists into a big list in last-in first-out fashion (values of firstly created will be in the last positions of ). We then traverse and print out the values of the list in the forwarding direction. The time complexity of this algorithm is as each node is visited only once.