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.