Problem $1.\backslash ((1+1+8+3+2=15\backslash )$ points$)$ Most Powerful Immortal in Acydia

In the magical world of Acydia, there are immortals who have become one with the universe by developing an innate understanding of its mysteries. You aspire to become the most powerful immortal of them all and you can, if you can properly utilize The Book.

Each page $\backslash ($ p $\backslash )$ of The Book contains a detailed description of a single unique technique you could choose to learn. After that description, $\backslash ($ p $\backslash )$ contains a list of those pages that each contain a more advanced technique that becomes available to you once you learn the technique described on page $\backslash ($ p$^\{1\}\backslash ).$ Some pages have empty lists signifying an end to the journey and that you have become immortal. One does end up living forever, but incapable of learning more techniques. And as everyone knows, the more techniques you know, the more powerful you are.

A path to immortality starts from the first page of The Book and may proceed to a page on its list. You can go from a page to another only if the latter is in the list of the former. For most aspirants, the inability to plan your path to immortality means that one often gets stuck knowing only an average number of techniques with no more advanced techniques to become more powerful.

Model the contents of The Book as a graph and frame "find a path to immortality that will allow you to learn the largest number of techniques possible" as a graph problem.

a$)$ What representation of graphs is most natural for The Book?

b$)$ Formalize the graph problem to be solved to become "the most powerful immortal".

c$)$ Present an algorithm for the graph problem you described in the previous subpart. Provide both pseudocode and a few sentences describing your algorithm.

$($Hint: Acydia $\backslash (\backslash$longrightarrow $\backslash )$ Acyclic Digraphs. Path to immortality $\backslash (\backslash$longrightarrow $\backslash )$ ordering of techniques.$)$

d$)$ Justify the correctness of your algorithm. Your justification does not need to be long or formal, just convincing.

e$)$ Analyze the running time of the algorithm.