Clone Graph — sao chép sâu một đồ thị có chu trình? Làm sao tránh lặp vô hạn?

Ý tưởng: DFS (hoặc BFS) kèm một HashMap old → new. Trước khi đi vào hàng xóm, tạo bản sao của node hiện tại và lưu vào map. Gặp lại node đã có trong map thì trả về bản sao đó thay vì đi tiếp.

Vì sao cần map: đồ thị có chu trình; nếu cứ clone mù sẽ lặp vô hạn. Map vừa đóng vai trò "visited", vừa giữ liên kết bản gốc–bản sao để nối cạnh đúng.

class GNode { val: number; neighbors: GNode[] = []; constructor(v: number){ this.val = v } }

function cloneGraph(node: GNode | null): GNode | null {
  const map = new Map<GNode, GNode>()
  const dfs = (n: GNode): GNode => {
    if (map.has(n)) return map.get(n)!
    const copy = new GNode(n.val)
    map.set(n, copy) // lưu TRƯỚC khi duyệt hàng xóm
    for (const nei of n.neighbors) copy.neighbors.push(dfs(nei))
    return copy
  }
  return node ? dfs(node) : null
}

Độ phức tạp: thời gian O(V+E), bộ nhớ O(V).

Lưu ý: Phải map.set trước vòng lặp hàng xóm — nếu set sau, một cạnh vòng về chính node đang clone sẽ tạo bản sao thứ hai và sai.

Idea: DFS (or BFS) with a HashMap old → new. Before recursing into neighbors, create the copy of the current node and store it in the map. If a node is already in the map, return its copy instead of recursing.

Why the map: the graph has cycles; cloning blindly loops forever. The map acts as "visited" and keeps the original–copy link so edges connect correctly.

class GNode { val: number; neighbors: GNode[] = []; constructor(v: number){ this.val = v } }

function cloneGraph(node: GNode | null): GNode | null {
  const map = new Map<GNode, GNode>()
  const dfs = (n: GNode): GNode => {
    if (map.has(n)) return map.get(n)!
    const copy = new GNode(n.val)
    map.set(n, copy) // store BEFORE visiting neighbors
    for (const nei of n.neighbors) copy.neighbors.push(dfs(nei))
    return copy
  }
  return node ? dfs(node) : null
}

Complexity: time O(V+E), space O(V).

Note: You must map.set before the neighbor loop — set it after and a self-referencing cycle creates a second copy and breaks.