Constructing a directed graph for O(1) queries
Make a Node class whose objects hold and an array of references to the other nodes they connects to. Make a Graph class whose objects store a dictionary mapping node IDs to nodes, and implement your 3 methods.