Graph patterns

function buildGraph(n, edges, { directed = false, weighted = false } = {}) {  const g = Array.from({ length: n }, () => []);  for (const [u, v, w] of edges) {    g[u].push(weighted ? [v, w] : v);    if (!directed) g[v].push(weighted ? [u, w] : u);  }  return g;}

//   queue = [src]; visited = {src}; parent = {src: null}//   while queue: u = dequeue//     for v in adj[u]: if v not visited: visited.add(v); parent[v] = u; enqueue(v)//   path: walk parent[] from target back to src, reverse.

function bfsPath(g, src, dst) {  const parent = new Map([[src, null]]), q = [src];  for (let h = 0; h < q.length; h++) { // head index = O(1) dequeue    const u = q[h];    if (u === dst) break;    for (const v of g[u]) if (!parent.has(v)) { parent.set(v, u); q.push(v); }  }  if (!parent.has(dst)) return [];  const path = [];  for (let x = dst; x !== null; x = parent.get(x)) path.push(x);  return path.reverse();}const g1 = buildGraph(6, [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]);

//                 iterative  stack=[src]; while stack: u=pop; if visited skip; mark; push neighbors

function dfsRec(g, u, seen = new Set(), out = []) {  seen.add(u); out.push(u);  for (const v of g[u]) if (!seen.has(v)) dfsRec(g, v, seen, out);  return out;}function dfsIter(g, src) {  const seen = new Set(), out = [], st = [src];  while (st.length) {    const u = st.pop();    if (seen.has(u)) continue;    seen.add(u); out.push(u);    for (let i = g[u].length - 1; i >= 0; i--) if (!seen.has(g[u][i])) st.push(g[u][i]); // reverse push = same order as recursive  }  return out;}

function countComponents(n, edges) {  const g = buildGraph(n, edges), seen = new Set();  let count = 0;  for (let i = 0; i < n; i++) if (!seen.has(i)) { count++; dfsRec(g, i, seen); }  return count;}

const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];function numIslands(grid) {  const m = grid.length, n = m ? grid[0].length : 0;  const sink = (r, c) => {    if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] !== '1') return;    grid[r][c] = '0';    for (const [dr, dc] of DIRS) sink(r + dr, c + dc);  };  let count = 0;  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) if (grid[r][c] === '1') { count++; sink(r, c); }  return count;}

function cloneGraph(node, map = new Map()) {  if (!node) return null;  if (map.has(node)) return map.get(node);  const copy = { val: node.val, neighbors: [] };  map.set(node, copy);  for (const nb of node.neighbors) copy.neighbors.push(cloneGraph(nb, map));  return copy;}const n1 = { val: 1, neighbors: [] }, n2 = { val: 2, neighbors: [n1] };n1.neighbors.push(n2);const c1 = cloneGraph(n1);

function hasCycleDirected(n, edges) {  const g = buildGraph(n, edges, { directed: true }), color = new Array(n).fill(0);  const dfs = (u) => {    color[u] = 1;    for (const v of g[u]) {      if (color[v] === 1) return true;      if (color[v] === 0 && dfs(v)) return true;    }    color[u] = 2;    return false;  };  for (let i = 0; i < n; i++) if (color[i] === 0 && dfs(i)) return true;  return false;}

function hasCycleUndirected(n, edges) {  const g = buildGraph(n, edges), seen = new Set();  const dfs = (u, p) => {    seen.add(u);    for (const v of g[u]) {      if (!seen.has(v)) { if (dfs(v, u)) return true; }      else if (v !== p) return true;    }    return false;  };  for (let i = 0; i < n; i++) if (!seen.has(i) && dfs(i, -1)) return true;  return false;}

//        If result.length < n -> cycle. Course Schedule I = "is length n"; II = the order itself.function topoKahn(n, edges) {  const g = buildGraph(n, edges, { directed: true }), indeg = new Array(n).fill(0);  for (const [, v] of edges) indeg[v]++;  const q = [];  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);  const order = [];  for (let h = 0; h < q.length; h++) {    const u = q[h]; order.push(u);    for (const v of g[u]) if (--indeg[v] === 0) q.push(v);  }  return order.length === n ? order : []; // [] => cycle}const canFinish = (n, prereqs) => topoKahn(n, prereqs.map(([a, b]) => [b, a])).length === n; // [course, prereq] -> edge prereq->course

function topoDFS(n, edges) {  const g = buildGraph(n, edges, { directed: true }), state = new Array(n).fill(0), out = [];  const dfs = (u) => {    state[u] = 1;    for (const v of g[u]) { if (state[v] === 1) throw new Error('cycle'); if (state[v] === 0) dfs(v); }    state[u] = 2; out.push(u);  };  try { for (let i = 0; i < n; i++) if (state[i] === 0) dfs(i); } catch { return []; }  return out.reverse();}const t = topoDFS(4, [[0, 1], [0, 2], [1, 3], [2, 3]]);

class MinHeap { // minimal inline heap on [key, ...] tuples  a = [];  push(x) { const a = this.a; a.push(x); for (let i = a.length - 1, p; i > 0 && a[p = (i - 1) >> 1][0] > a[i][0]; i = p) [a[i], a[p]] = [a[p], a[i]]; }  pop() {    const a = this.a, top = a[0], last = a.pop();    if (a.length) { a[0] = last; for (let i = 0;;) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < a.length && a[l][0] < a[m][0]) m = l; if (r < a.length && a[r][0] < a[m][0]) m = r; if (m === i) break; [a[i], a[m]] = [a[m], a[i]]; i = m; } }    return top;  }  get size() { return this.a.length; }}function dijkstra(n, edges, src) {  const g = buildGraph(n, edges, { directed: true, weighted: true }), dist = new Array(n).fill(Infinity);  const hp = new MinHeap();  dist[src] = 0; hp.push([0, src]);  while (hp.size) {    const [d, u] = hp.pop();    if (d > dist[u]) continue; // stale    for (const [v, w] of g[u]) if (d + w < dist[v]) { dist[v] = d + w; hp.push([dist[v], v]); }  }  return dist;}

//        SAY: "handles negative edge weights; Dijkstra does not."function bellmanFord(n, edges, src) {  const dist = new Array(n).fill(Infinity);  dist[src] = 0;  for (let i = 0; i < n - 1; i++) for (const [u, v, w] of edges) if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;  for (const [u, v, w] of edges) if (dist[u] + w < dist[v]) return null; // negative cycle  return dist;}

class UnionFind {  constructor(n) { this.parent = Array.from({ length: n }, (_, i) => i); this.rank = new Array(n).fill(0); this.count = n; }  find(x) { while (this.parent[x] !== x) { this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x]; } return x; } // path halving  union(a, b) {    let ra = this.find(a), rb = this.find(b);    if (ra === rb) return false;    if (this.rank[ra] < this.rank[rb]) [ra, rb] = [rb, ra];    this.parent[rb] = ra;    if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;    this.count--;    return true;  }  connected(a, b) { return this.find(a) === this.find(b); }}const uf = new UnionFind(5);uf.union(0, 1); uf.union(1, 2); uf.union(3, 4);

//        Prim's: grow from one node with a min-heap of crossing edges; O(E log V). Same MST weight.function kruskal(n, edges) {  const uf = new UnionFind(n);  let total = 0, used = 0;  for (const [u, v, w] of [...edges].sort((a, b) => a[2] - b[2])) if (uf.union(u, v)) { total += w; used++; }  return used === n - 1 ? total : -1; // -1 = disconnected}

function isBipartite(g) {  const color = new Array(g.length).fill(0);  for (let s = 0; s < g.length; s++) {    if (color[s]) continue;    color[s] = 1;    const q = [s];    for (let h = 0; h < q.length; h++) for (const v of g[q[h]]) {      if (color[v] === color[q[h]]) return false;      if (!color[v]) { color[v] = -color[q[h]]; q.push(v); }    }  }  return true;}

function ladderLength(begin, end, wordList) {  const dict = new Set(wordList);  if (!dict.has(end)) return 0;  const q = [[begin, 1]];  dict.delete(begin);  for (let h = 0; h < q.length; h++) {    const [w, d] = q[h];    if (w === end) return d;    for (let i = 0; i < w.length; i++) for (let c = 97; c <= 122; c++) {      const nw = w.slice(0, i) + String.fromCharCode(c) + w.slice(i + 1);      if (dict.delete(nw)) q.push([nw, d + 1]); // delete = visit    }  }  return 0;}