787. Cheapest Flights Within K Stops☆

class _Node {
  val: number;
  neighbors: _Node[];
  constructor(val = 0, neighbors: _Node[] = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}

function cloneGraph(node: _Node | null): _Node | null {
  if (!node) return null;

  // Map from original node → its deep clone.
  // It serves two roles at once: visited set AND clone registry.
  const cloneMap = new Map<_Node, _Node>();

  const queue: _Node[] = [node];
  cloneMap.set(node, new _Node(node.val));

  while (queue.length > 0) {
    const cur = queue.shift()!;
    const curClone = cloneMap.get(cur)!;

    for (const neighbor of cur.neighbors) {
      if (!cloneMap.has(neighbor)) {
        // First visit: create the clone and enqueue the original.
        cloneMap.set(neighbor, new _Node(neighbor.val));
        queue.push(neighbor);
      }
      // Whether brand-new or already seen, wire the edge.
      curClone.neighbors.push(cloneMap.get(neighbor)!);
    }
  }

  return cloneMap.get(node)!;
}

function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number
): number {
  const INF = Infinity;
  // dist[i] = cheapest cost to reach city i using at most (round) edges so far
  let dist: number[] = Array(n).fill(INF);
  dist[src] = 0;

  for (let round = 0; round < k + 1; round++) {
    // Snapshot: each round can only use prices from the PREVIOUS round.
    // Without this copy, a chain of updates within one round would let us
    // traverse more than 1 edge per round — violating the k-stop constraint.
    const prev = [...dist];

    for (const [from, to, cost] of flights) {
      if (prev[from] === INF) continue;            // city not yet reachable
      if (prev[from] + cost < dist[to]) {
        dist[to] = prev[from] + cost;
      }
    }
  }

  return dist[dst] === INF ? -1 : dist[dst];
}

function countComponents(n: number, edges: number[][]): number {
  const parent = Array.from({ length: n }, (_, i) => i);

  function find(x: number): number {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path compression (halving)
      x = parent[x];
    }
    return x;
  }

  function union(a: number, b: number): boolean {
    const ra = find(a);
    const rb = find(b);
    if (ra === rb) return false; // already connected
    parent[rb] = ra;             // merge rb's tree under ra
    return true;
  }

  let components = n;
  for (const [a, b] of edges) {
    if (union(a, b)) components--; // successful merge = one fewer component
  }
  return components;
}

function wallsAndGates(rooms: number[][]): void {
  const INF = 2147483647;
  const rows = rooms.length;
  const cols = rows > 0 ? rooms[0].length : 0;
  const queue: [number, number][] = [];

  // Seed: enqueue every gate (distance 0)
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (rooms[r][c] === 0) queue.push([r, c]);
    }
  }

  // BFS: each wave is one step farther from the nearest gate
  const DIRS: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (rooms[nr][nc] !== INF) continue;   // wall or already settled
      rooms[nr][nc] = rooms[r][c] + 1;       // BFS guarantees shortest
      queue.push([nr, nc]);
    }
  }
}