ekgns33.java

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
  public Node cloneGraph(Node node) {
    Map<Integer, Node> nodeMap = new HashMap<>();
    if(node == null) return null;
    boolean[] visited = new boolean[101];
    dfsHelper(nodeMap, node, visited);
    return nodeMap.get(1);
  }

  private void dfsHelper(Map<Integer, Node> map, Node node, boolean[] visited) {
    if(!map.containsKey(node.val)) {
      map.put(node.val, new Node(node.val));
    }
    visited[node.val] = true;
    Node cur = map.get(node.val);
    for(Node adjacent : node.neighbors) {
      map.putIfAbsent(adjacent.val, new Node(adjacent.val));
      cur.neighbors.add(map.get(adjacent.val));
      if(!visited[adjacent.val]) dfsHelper(map, adjacent, visited);
    }
  }
}