Graphs

const n = 4;
const edges: [number, number][] = [
  [0, 1], [0, 2], [1, 2], [2, 3],
];
 
const adj = Array.from({ length: n }, (): number[] => []);
for (const [u, v] of edges) {
  adj[u].push(v); // undirected: both directions
  adj[v].push(u);
}
adj; // [[1, 2], [0, 2], [0, 1, 3], [2]]
 
const sets = adj.map((vs) => new Set(vs));
sets[0].has(1); // true: an O(1) edge test
 
const matrix = adj.map(() => new Uint8Array(n));
for (const [u, v] of edges) matrix[u][v] = matrix[v][u] = 1;
[...matrix[2]]; // [1, 1, 0, 1]
 
// CSR: u's neighbors sit in targets from start[u] up to
// (not including) start[u + 1]
const start = new Int32Array(n + 1);
adj.forEach((vs, u) => {
  start[u + 1] = start[u] + vs.length;
});
const targets = Int32Array.from(adj.flat());
[...start]; // [0, 2, 4, 7, 8]
[...targets.subarray(start[2], start[3])]; // [0, 1, 3]
 
const roads = new Map([
  ["a", new Map([["b", 4], ["c", 1]])],
  ["c", new Map([["b", 2]])],
]);
roads.get("a")?.get("c"); // 1: the weight of a -> c

// n and m, then m edges; node ids start at one
const raw = "4 3\n1 2\n2 3\n3 1";
const [first, ...lines] = raw.split("\n");
const [n, m] = first.split(" ").map(Number);
const adj = Array.from(
  { length: n + 1 },
  (): number[] => [],
);
for (const line of lines.slice(0, m)) {
  const [u, v] = line.split(" ").map(Number);
  adj[u].push(v);
  adj[v].push(u);
}
adj.slice(1);
// [[2, 3], [1, 3], [2, 1], []]: node 4 has no edges
 
function addEdge(
  g: Map<string, string[]>,
  u: string,
  v: string,
): void {
  let list = g.get(u);
  if (!list) g.set(u, (list = [])); // get or create
  list.push(v);
}
const g = new Map<string, string[]>();
addEdge(g, "a", "b");
g.has("b"); // false: b has no entry of its own
g.get("b") ?? []; // []: reads without inserting
 
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
 
function* gridNeighbors(
  grid: readonly string[],
  r: number,
  c: number,
): Generator<[number, number]> {
  for (const [dr, dc] of DIRS) {
    const nr = r + dr;
    const nc = c + dc;
    const inside = nr >= 0 && nr < grid.length &&
      nc >= 0 && nc < grid[0].length;
    if (inside && grid[nr][nc] !== "#") yield [nr, nc];
  }
}
[...gridNeighbors(["..#", ".#."], 0, 1)]; // [[0, 0]]

const obj: Record<string, string[]> = {};
"constructor" in obj; // true: inherited, not a node
Object.hasOwn(obj, "constructor"); // false
const byId: Record<number, string> = { 1: "a" };
byId["1"]; // "a": the key 1 was stored as "1"

type Adj = readonly (readonly number[])[];
 
function bfs(adj: Adj, src: number): Int32Array {
  const dist = new Int32Array(adj.length).fill(-1);
  dist[src] = 0;
  const queue = [src];
  // a head index instead of queue.shift(), which is O(n)
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    for (const v of adj[u]) {
      if (dist[v] === -1) { // mark when enqueued
        dist[v] = dist[u] + 1;
        queue.push(v);
      }
    }
  }
  return dist;
}
 
function levels(adj: Adj, src: number): number[][] {
  const seen = new Set([src]);
  const out: number[][] = [];
  for (let level = [src]; level.length > 0; ) {
    out.push(level);
    const next: number[] = [];
    for (const u of level) {
      for (const v of adj[u]) {
        if (!seen.has(v)) {
          seen.add(v);
          next.push(v);
        }
      }
    }
    level = next;
  }
  return out;
}
 
const adj: Adj = [
  [1, 2], [0, 3], [0, 3], [1, 2, 4], [3], [],
];
[...bfs(adj, 0)]; // [0, 1, 1, 2, 3, -1]
levels(adj, 0); // [[0], [1, 2], [3], [4]]

const adj = [[1, 2], [0, 3], [0, 3], [1, 2, 4], [3], []];
const seen = new Set([0]);
for (const u of seen) { // also visits values added below
  for (const v of adj[u]) seen.add(v);
}
[...seen]; // [0, 1, 2, 3, 4]: BFS order
 
type WAdj01 = readonly (readonly [to: number, w: 0 | 1])[][];
 
function zeroOneBfs(adj: WAdj01, src: number): number[] {
  const dist = adj.map(() => Infinity);
  dist[src] = 0;
  let level = [src];
  for (let d = 0; level.length > 0; d++) {
    const next: number[] = [];
    // level grows while it is scanned: 0-edges stay at d
    for (let i = 0; i < level.length; i++) {
      const u = level[i];
      if (dist[u] !== d) continue; // stale: improved since
      for (const [v, w] of adj[u]) {
        if (d + w < dist[v]) {
          dist[v] = d + w;
          (w === 0 ? level : next).push(v);
        }
      }
    }
    level = next;
  }
  return dist;
}
const wadj: WAdj01 = [
  [[1, 1], [2, 0]], [[3, 1]], [[1, 0]], [],
];
zeroOneBfs(wadj, 0); // [0, 0, 0, 1]

type Adj = readonly (readonly number[])[];
 
function countReachable(adj: Adj, src: number): number {
  const seen = new Uint8Array(adj.length);
  let count = 0;
  const dfs = (u: number): void => { // recursive
    seen[u] = 1;
    count++;
    for (const v of adj[u]) if (!seen[v]) dfs(v);
  };
  dfs(src);
  return count;
}
 
function preorder(adj: Adj, src: number): number[] {
  const seen = new Uint8Array(adj.length);
  const order: number[] = [];
  const stack = [src];
  while (stack.length > 0) {
    const u = stack.pop()!;
    if (seen[u]) continue; // pushed twice; done already
    seen[u] = 1; // mark on pop: the order recursion gives
    order.push(u);
    const vs = adj[u];
    // push in reverse so the first neighbor is on top
    for (let i = vs.length - 1; i >= 0; i--) {
      stack.push(vs[i]);
    }
  }
  return order;
}
 
function postorder(adj: Adj, src: number): number[] {
  const next = new Int32Array(adj.length); // cursor per node
  const seen = new Uint8Array(adj.length);
  const out: number[] = [];
  const stack = [src];
  seen[src] = 1;
  while (stack.length > 0) {
    const u = stack[stack.length - 1];
    if (next[u] < adj[u].length) {
      const v = adj[u][next[u]++]; // resume u's scan
      if (!seen[v]) {
        seen[v] = 1;
        stack.push(v);
      }
    } else {
      stack.pop(); // no neighbor left: u is finished
      out.push(u);
    }
  }
  return out;
}
 
const dag: Adj = [[1, 2], [3], [3], []];
countReachable(dag, 0); // 4
preorder(dag, 0); // [0, 1, 3, 2]
postorder(dag, 0); // [3, 1, 2, 0]
postorder(dag, 0).reverse(); // [0, 2, 1, 3]: a topo order

class Heap<T> {
  private a: T[];
  private cmp: (x: T, y: T) => number;
  constructor(
    cmp: (x: T, y: T) => number,
    items: Iterable<T> = [],
  ) {
    this.cmp = cmp;
    this.a = [...items];
    for (let i = (this.a.length >> 1) - 1; i >= 0; i--) {
      this.down(i);
    }
  }
  get size(): number {
    return this.a.length;
  }
  peek(): T | undefined {
    return this.a[0];
  }
  push(x: T): void {
    const a = this.a;
    let i = a.push(x) - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.cmp(a[i], a[p]) >= 0) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a;
    if (a.length <= 1) return a.pop();
    const top = a[0];
    a[0] = a.pop()!;
    this.down(0);
    return top;
  }
  private down(i: number): void {
    const a = this.a;
    for (;;) {
      const l = 2 * i + 1;
      let m = i;
      if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
      const r = l + 1;
      if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
      if (m === i) return;
      [a[i], a[m]] = [a[m], a[i]];
      i = m;
    }
  }
}
 
type WAdj = readonly (readonly [to: number, w: number])[][];
 
function dijkstra(adj: WAdj, src: number) {
  const dist = new Float64Array(adj.length).fill(Infinity);
  const parent = new Int32Array(adj.length).fill(-1);
  dist[src] = 0;
  const heap = new Heap<[d: number, u: number]>(
    (x, y) => x[0] - y[0],
    [[0, src]],
  );
  while (heap.size > 0) {
    const [d, u] = heap.pop()!;
    if (d > dist[u]) continue; // stale: u improved later
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) {
        dist[v] = d + w;
        parent[v] = u;
        heap.push([d + w, v]);
      }
    }
  }
  return { dist, parent };
}
 
function pathTo(parent: Int32Array, t: number): number[] {
  const out: number[] = [];
  for (; t !== -1; t = parent[t]) out.push(t);
  return out.reverse();
}
 
const adj: WAdj = [
  [[1, 4], [2, 1]],
  [[3, 1]],
  [[1, 2], [3, 5]],
  [],
];
const { dist, parent } = dijkstra(adj, 0);
[...dist]; // [0, 3, 1, 4]
pathTo(parent, 3); // [0, 2, 1, 3]

[10, 1] < [9, 1]; // true: compares "10,1" with "9,1"
new Int32Array(2).fill(Infinity); // Int32Array [0, 0]
 
type WEdge = readonly [u: number, v: number, w: number];
 
function bellmanFord(
  n: number,
  edges: readonly WEdge[],
  src: number,
  rounds: number,
): Float64Array {
  let dist = new Float64Array(n).fill(Infinity);
  dist[src] = 0;
  for (let r = 0; r < rounds; r++) {
    const next = dist.slice(); // read last round's values
    for (const [u, v, w] of edges) {
      if (dist[u] + w < next[v]) next[v] = dist[u] + w;
    }
    dist = next;
  }
  return dist;
}
 
const flights: WEdge[] = [
  [0, 1, 100], [1, 2, 100], [0, 2, 500],
];
bellmanFord(3, flights, 0, 3 - 1)[2]; // 200
bellmanFord(3, flights, 0, 1)[2]; // 500: one edge at most
 
const N = 3;
const d = Array.from({ length: N }, (): number[] =>
  Array(N).fill(Infinity),
);
for (let i = 0; i < N; i++) d[i][i] = 0;
const wEdges: WEdge[] = [[0, 1, 4], [1, 2, -2], [0, 2, 5]];
for (const [u, v, w] of wEdges) {
  d[u][v] = Math.min(d[u][v], w);
}
for (let k = 0; k < N; k++) { // Floyd–Warshall: k outermost
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      const via = d[i][k] + d[k][j];
      if (via < d[i][j]) d[i][j] = via;
    }
  }
}
d[0]; // [0, 4, 2]

type Edge = readonly [u: number, v: number]; // u before v
 
function kahn(
  n: number,
  edges: readonly Edge[],
): number[] | null {
  const adj = Array.from({ length: n }, (): number[] => []);
  const indeg = new Int32Array(n);
  for (const [u, v] of edges) {
    adj[u].push(v);
    indeg[v]++;
  }
  const order: number[] = [];
  for (let u = 0; u < n; u++) {
    if (indeg[u] === 0) order.push(u);
  }
  for (let head = 0; head < order.length; head++) {
    for (const v of adj[order[head]]) {
      if (--indeg[v] === 0) order.push(v);
    }
  }
  return order.length === n ? order : null; // short: a cycle
}
 
const deps: Edge[] = [
  [4, 2], [5, 2], [5, 0], [2, 3], [0, 3], [3, 1],
];
kahn(6, deps); // [4, 5, 2, 0, 3, 1]
kahn(2, [[0, 1], [1, 0]]); // null

class DSU {
  readonly parent: Int32Array;
  readonly size: Int32Array;
  count: number; // number of components
 
  constructor(n: number) {
    this.parent = new Int32Array(n).map((_, i) => i);
    this.size = new Int32Array(n).fill(1);
    this.count = n;
  }
 
  find(x: number): number {
    const p = this.parent;
    while (p[x] !== x) {
      p[x] = p[p[x]]; // path halving
      x = p[x];
    }
    return x;
  }
 
  union(a: number, b: number): boolean {
    let ra = this.find(a);
    let rb = this.find(b);
    if (ra === rb) return false; // same set: a cycle edge
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra; // hang the smaller tree
    this.size[ra] += this.size[rb];
    this.count--;
    return true;
  }
}
 
const dsu = new DSU(5);
[dsu.union(0, 1), dsu.union(1, 2), dsu.union(0, 2)];
// [true, true, false]: the third edge closes a cycle
dsu.count; // 3: {0, 1, 2}, {3}, {4}
 
const d6 = new DSU(6);
d6.union(0, 1);
d6.union(2, 3);
d6.union(1, 3); // true: root 2 hangs under 0
d6.union(4, 5);
d6.find(3); // 0, and the path is halved: parent[3] = 0
d6.union(3, 5); // true: root 4 hangs under 0
d6.union(1, 4); // false: already one set
[...d6.parent]; // [0, 0, 0, 0, 0, 4]

class UnionFind<T> {
  private parent = new Map<T, T>();
 
  find(x: T): T {
    const parent = this.parent;
    if (!parent.has(x)) parent.set(x, x); // first sight
    let p = parent.get(x)!;
    while (p !== x) {
      const grand = parent.get(p)!;
      parent.set(x, grand); // path halving
      x = grand;
      p = parent.get(x)!;
    }
    return x;
  }
 
  union(a: T, b: T): boolean {
    const ra = this.find(a);
    const rb = this.find(b);
    if (ra === rb) return false;
    this.parent.set(ra, rb);
    return true;
  }
}
 
const people = new UnionFind<string>();
people.union("ann", "bo");
[people.find("ann") === people.find("bo"),
  people.find("cy") === people.find("bo")];
// [true, false]

type WEdge = readonly [u: number, v: number, w: number];
 
function kruskal(n: number, edges: readonly WEdge[]) {
  const parent = new Int32Array(n).map((_, i) => i);
  const find = (x: number): number => {
    // path halving: x jumps to its grandparent
    while (parent[x] !== x) {
      x = parent[x] = parent[parent[x]];
    }
    return x;
  };
  const tree: WEdge[] = [];
  let total = 0;
  for (const e of edges.toSorted((a, b) => a[2] - b[2])) {
    const ru = find(e[0]);
    const rv = find(e[1]);
    if (ru === rv) continue; // would close a cycle
    parent[ru] = rv;
    tree.push(e);
    total += e[2];
  }
  // fewer than n - 1 edges: the graph is disconnected
  return { total, tree };
}
 
type Matrix = readonly (readonly number[])[];
 
function primDense(w: Matrix): number {
  const n = w.length;
  // best[v]: the cheapest edge from the tree to v
  const best = new Float64Array(n).fill(Infinity);
  const inTree = new Uint8Array(n);
  best[0] = 0;
  let total = 0;
  for (let k = 0; k < n; k++) {
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (inTree[v]) continue;
      if (u === -1 || best[v] < best[u]) u = v;
    }
    inTree[u] = 1;
    total += best[u]; // Infinity: the graph is disconnected
    for (let v = 0; v < n; v++) {
      if (!inTree[v] && w[u][v] < best[v]) best[v] = w[u][v];
    }
  }
  return total;
}
 
const edges: WEdge[] = [
  [0, 1, 4], [0, 2, 1], [1, 2, 2], [1, 3, 5], [2, 3, 8],
];
kruskal(4, edges);
// { total: 8, tree: [[0, 2, 1], [1, 2, 2], [1, 3, 5]] }
 
const I = Infinity;
const w = [
  [I, 4, 1, I],
  [4, I, 2, 5],
  [1, 2, I, 8],
  [I, 5, 8, I],
];
primDense(w); // 8

type Adj = readonly (readonly number[])[];
 
function allPaths(adj: Adj, target: number): number[][] {
  const out: number[][] = [];
  const path = [0];
  const go = (u: number): void => {
    if (u === target) {
      out.push([...path]); // copy: path keeps changing
      return;
    }
    for (const v of adj[u]) {
      path.push(v);
      go(v);
      path.pop();
    }
  };
  go(0);
  return out;
}
 
function countPaths(adj: Adj, target: number): number {
  const memo = new Map<number, number>(); // a DAG: no cycles
  const ways = (u: number): number => {
    if (u === target) return 1;
    let total = memo.get(u);
    if (total === undefined) {
      total = 0;
      for (const v of adj[u]) total += ways(v);
      memo.set(u, total);
    }
    return total;
  };
  return ways(0);
}
 
const dag: Adj = [[1, 2], [3], [3], []];
allPaths(dag, 3); // [[0, 1, 3], [0, 2, 3]]
countPaths(dag, 3); // 2

function bfsOrder<T>(
  g: ReadonlyMap<T, Iterable<T>>,
  start: T,
): T[] {
  const seen = new Set([start]);
  const order = [start];
  for (const u of order) { // also visits pushed items
    for (const v of g.get(u) ?? []) {
      if (!seen.has(v)) {
        seen.add(v);
        order.push(v);
      }
    }
  }
  return order;
}
 
const g = new Map([["a", ["b", "c"]], ["b", ["d"]]]);
bfsOrder(g, "a"); // ["a", "b", "c", "d"]
const adj = [[1], [0, 2], []];
bfsOrder(new Map(adj.entries()), 0); // [0, 1, 2]
 
type Neighbor = readonly [to: number, w: number];
const wadj: Neighbor[][] = [[[1, 5]], []];
// inferred as plain nested number arrays:
const loose = [[[1, 5]], []];
const [to, w] = wadj[0][0]; // to: number, w: number
// @ts-expect-error: plain arrays lack the tuple shape
const strict: Neighbor[][] = loose;

const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
 
function numIslands(grid: readonly string[][]): number {
  const rows = grid.length;
  const cols = grid[0]?.length ?? 0;
  // one id per cell: r * cols + c
  const seen = new Uint8Array(rows * cols);
  let islands = 0;
  for (let r0 = 0; r0 < rows; r0++) {
    for (let c0 = 0; c0 < cols; c0++) {
      const id0 = r0 * cols + c0;
      if (seen[id0] || grid[r0][c0] !== "1") continue;
      islands++;
      seen[id0] = 1;
      const stack = [id0];
      while (stack.length > 0) {
        const id = stack.pop()!;
        const r = Math.floor(id / cols);
        const c = id % cols;
        for (const [dr, dc] of DIRS) {
          const nr = r + dr;
          const nc = c + dc;
          if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
            continue;
          }
          const nid = nr * cols + nc;
          if (!seen[nid] && grid[nr][nc] === "1") {
            seen[nid] = 1;
            stack.push(nid);
          }
        }
      }
    }
  }
  return islands;
}
 
const sea = ["11000", "11000", "00100", "00011"];
numIslands(sea.map((row) => [...row])); // 3
const strip = (n: number) => ["1".repeat(n).split("")];
numIslands(strip(100_000)); // 1: no recursion needed

type Prereq = readonly [course: number, before: number];
 
function rounds(
  n: number,
  prereqs: readonly Prereq[],
): number[][] | null {
  const adj = Array.from({ length: n }, (): number[] => []);
  const indeg = new Int32Array(n);
  for (const [course, before] of prereqs) {
    adj[before].push(course); // before -> course
    indeg[course]++;
  }
  const out: number[][] = [];
  let ready: number[] = [];
  for (let u = 0; u < n; u++) {
    if (indeg[u] === 0) ready.push(u);
  }
  let done = 0;
  while (ready.length > 0) {
    out.push(ready);
    done += ready.length;
    const next: number[] = [];
    for (const u of ready) {
      for (const v of adj[u]) {
        if (--indeg[v] === 0) next.push(v);
      }
    }
    ready = next;
  }
  return done === n ? out : null; // null: a cycle
}
 
rounds(4, [[1, 0], [2, 0], [3, 1], [3, 2]]);
// [[0], [1, 2], [3]]: three semesters
rounds(2, [[1, 0], [0, 1]]); // null

class GraphNode {
  val: number;
  neighbors: GraphNode[] = [];
  constructor(val: number) {
    this.val = val;
  }
}
 
function cloneGraph(
  start: GraphNode | null,
): GraphNode | null {
  if (!start) return null;
  const copies = new Map<GraphNode, GraphNode>();
  copies.set(start, new GraphNode(start.val));
  const stack = [start];
  while (stack.length > 0) {
    const old = stack.pop()!;
    const copy = copies.get(old)!;
    for (const nb of old.neighbors) {
      let c = copies.get(nb);
      if (!c) { // create on first sight
        c = new GraphNode(nb.val);
        copies.set(nb, c);
        stack.push(nb);
      }
      copy.neighbors.push(c);
    }
  }
  return copies.get(start)!;
}
 
const [a, b, c] = [1, 2, 3].map((v) => new GraphNode(v));
a.neighbors = [b, c];
b.neighbors = [a, c];
c.neighbors = [a, b];
const a2 = cloneGraph(a)!;
[a2.val, a2.neighbors.map((nb) => nb.val)]; // [1, [2, 3]]
[a2 !== a, a2.neighbors[0].neighbors[0] === a2];
// [true, true]: a new graph with the same shape

function accountsMerge(accounts: string[][]): string[][] {
  const parent = new Map<string, string>();
  const find = (x: string): string => {
    if (!parent.has(x)) parent.set(x, x);
    let p = parent.get(x)!;
    while (p !== x) {
      const grand = parent.get(p)!;
      parent.set(x, grand);
      x = grand;
      p = parent.get(x)!;
    }
    return x;
  };
  const owner = new Map<string, string>();
  for (const [name, first, ...rest] of accounts) {
    owner.set(first, name);
    find(first); // register one-email accounts too
    for (const email of rest) {
      owner.set(email, name);
      parent.set(find(email), find(first));
    }
  }
  const groups = Map.groupBy(owner.keys(), (e) => find(e));
  return [...groups.values()].map((emails) => [
    owner.get(emails[0])!,
    ...emails.sort(),
  ]);
}
 
const accounts = [
  ["ann", "a@x", "b@x"],
  ["ann", "a@x", "c@x"],
  ["bo", "d@x"],
  ["ann", "e@x"],
];
for (const row of accountsMerge(accounts)) console.log(row);
// ["ann", "a@x", "b@x", "c@x"]
// ["bo", "d@x"]
// ["ann", "e@x"]

const WHITE = 0; // unseen
const GRAY = 1; // on the current path
const BLACK = 2; // finished
 
type Adj = readonly (readonly number[])[];
 
function hasCycle(adj: Adj): boolean {
  const color = new Uint8Array(adj.length);
  const next = new Int32Array(adj.length);
  for (let s = 0; s < adj.length; s++) {
    if (color[s] !== WHITE) continue;
    color[s] = GRAY;
    const stack = [s];
    while (stack.length > 0) {
      const u = stack[stack.length - 1];
      if (next[u] < adj[u].length) {
        const v = adj[u][next[u]++];
        if (color[v] === GRAY) return true; // back edge
        if (color[v] === WHITE) {
          color[v] = GRAY;
          stack.push(v);
        }
      } else {
        color[u] = BLACK; // every neighbor finished
        stack.pop();
      }
    }
  }
  return false;
}
 
hasCycle([[1], [2], [0]]); // true
hasCycle([[1, 2], [3], [3], []]); // false: a diamond
const chain = (n: number) =>
  Array.from({ length: n }, (_, i) =>
    i + 1 < n ? [i + 1] : [],
  );
hasCycle(chain(100_000)); // false, with no recursion