Clone a Directed Acyclic Graph (DAG)

[Question]
Write a function to copy a Directed Acyclic Graph (DAG) -- http://en.wikipedia.org/wiki/Directed_acyclic_graph.


class Node {
  int value;
  vector<Node *> neighbors;
};

Node *copyGraph(Node *root) {
   // add code here
}


[Analysis]
Using DFS (Depth First Search) and a recursive function. Note the copy of next node could be created before the DFS reaches it, so a hashmap is needed to record the nodes that have been created. 


In actual DAG, there may be many vertices which have no incoming edges. So there could be many starting vertices for DFS. This can be justified by using an extra node which reaches all starting vertices in the DAG. Using this extra node as root, the clone function will work the same.


The time complexity is O(n+m), n is number of vertices, m is number of edges.

[Solution]
// In Java

public class DAGraph {
public class Node {
int value;
List<Node> list;
}

public Node cloneDAGraph (Node root) {
return cloneDAGraph( root, new HashMap<Node,Node>() );
}

public Node cloneDAGraph (Node root, Map<Node, Node> map) {
if (root == null) return null;

if (map.containsKey(root)) return map.get(root);

Node newNode = new Node();
newNode.value = root.value;
newNode.list = new ArrayList<Node>();
map.put(root, newNode);

for(Node n: root.list) {
newNode.list.add(cloneDAGraph(n, map));
}
return newNode;
}
}