Deep copy graph(possible loops)

Make a deep copy of an undirected graph, there could be cycles in the original graph.

Assumptions

• The given graph is not null

Solution: HashMap to track pairs

Track <Original, Copy> pairs with hashmap.

DFS search each neighbor:

1. if Original not in hashmap.

2. Create new copy .

3. Insert copy into HashMap

4. Check all neighbors of copy(recursive)

5. add neighbor to copy.neighbor

/*
* class GraphNode {
*   public int key;
*   public List<GraphNode> neighbors;
*   public GraphNode(int key) {
*     this.key = key;
*     this.neighbors = new ArrayList<GraphNode>();
*   }
* }
*/
public class Solution {
  public List<GraphNode> copy(List<GraphNode> graph) {
    Map<GraphNode, GraphNode> hashmap = new HashMap<>();
    for (GraphNode node : graph){
      if (!hashmap.containsKey(node)){
        hashmap.put(node, new GraphNode(node.key)); //original copy pair
        dfs(node, hashmap);
      }
    }
    return new ArrayList<GraphNode>(hashmap.values());
  }

  private void dfs(GraphNode original, Map<GraphNode, GraphNode> hashmap){
    GraphNode copy = hashmap.get(original);
    for (GraphNode neighbor: original.neighbors){
      if (!hashmap.containsKey(neighbor)){
        hashmap.put(neighbor, new GraphNode(neighbor.key));
        dfs(neighbor, hashmap);
      }
      copy.neighbors.add(hashmap.get(neighbor));
    }
  }
}

TC: For N nodes, k connections each O(N*K)

SC: O(N*K)