Consider a DAG as a tree structure, maybe multiple root, even not connected,
(I don't if it is not connected, is it still DAG).
So, treat it like a tree. DAG has n nodes. We have all the nodes' references
. Each node has the storage of its parents ( immediate nodes where directed
edges are from). Each node also has the storage of its children ( immediate
nodes where the directed edges are toward).
The question is if we want to store the DAG with such a structure, what will
be the space complexity of node references?
Or DAG has other storage structure and the space complexity?