// ─────────────────────────────────────────────────────────────────────────────
// GRAPHS
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : nodes + edges; traverse (BFS/DFS), order (topo), connect (union-find), shortest paths.
// TELL   : "edges", "connected", "prerequisites / dependencies", "shortest path", "islands / grid",
//          "can reach", "cycle", "minimum spanning", "transform word to word".
// SAY    : adjacency list / matrix, BFS (level order, shortest in unweighted), DFS, visited set,
//          connected components, topological sort (Kahn's / DFS post-order), Dijkstra (non-negative),
//          Bellman-Ford (negative edges), union-find / disjoint set union (path compression, union by rank),
//          Kruskal / Prim (MST), bipartite (2-coloring), implicit graph.
// BIG-O  : BFS/DFS O(V + E); Dijkstra O((V + E) log V); Bellman-Ford O(VE); union-find ~O(alpha(n)) per op.
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── 1. Build adjacency list from edge list  —  Map node -> [neighbors] (or [[nbr, w]] weighted)  —  O(V + E)
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;
}
assert.deepEqual(buildGraph(3, [[0, 1], [1, 2]]), [[1], [0, 2], [1]]);
assert.deepEqual(buildGraph(3, [[0, 1, 5]], { directed: true, weighted: true }), [[[1, 5]], [], []]);

// ── BFS TEMPLATE (shortest path in unweighted graph; parent map for path reconstruction)
//   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.
// ── 2. BFS shortest path with reconstruction  —  O(V + E) / O(V)
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]]);
assert.deepEqual(bfsPath(g1, 0, 4), [0, 1, 3, 4]);
assert.deepEqual(bfsPath(g1, 0, 5), []); // unreachable
assert.deepEqual(bfsPath(g1, 2, 2), [2]);

// ── DFS TEMPLATE: recursive  dfs(u): visited.add(u); for v in adj[u]: if !visited: dfs(v)
//                 iterative  stack=[src]; while stack: u=pop; if visited skip; mark; push neighbors
// ── 3. DFS recursive + iterative (visit order)  —  O(V + E) / O(V)
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;
}
assert.deepEqual(dfsRec(g1, 0), [0, 1, 3, 2, 4]);
assert.deepEqual(dfsIter(g1, 0), [0, 1, 3, 2, 4]);
assert.deepEqual(dfsRec(buildGraph(1, []), 0), [0]);

// ── 4. Connected components (undirected)  —  DFS from every unvisited node; count starts  —  O(V + E)
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;
}
assert.equal(countComponents(5, [[0, 1], [1, 2], [3, 4]]), 2);
assert.equal(countComponents(3, []), 3);
assert.equal(countComponents(0, []), 0);

// ── 5. Number of islands (grid as graph)  —  DIRS array; DFS sinks visited land to '0'  —  O(mn) / O(mn) stack
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;
}
assert.equal(numIslands([['1', '1', '0'], ['0', '1', '0'], ['1', '0', '1']]), 3);
assert.equal(numIslands([['0']]), 0);
assert.equal(numIslands([]), 0);

// ── 6. Clone graph  —  DFS with Map original -> copy (also serves as visited)  —  O(V + E)
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);
assert.equal(c1.neighbors[0].val, 2);
assert.notEqual(c1.neighbors[0], n2);
assert.equal(c1.neighbors[0].neighbors[0], c1); // cycle preserved
assert.equal(cloneGraph(null), null);

// ── 7. Cycle detection, directed (3-color: WHITE unvisited, GRAY on stack, BLACK done)  —  back edge to GRAY = cycle  —  O(V + E)
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;
}
assert.equal(hasCycleDirected(3, [[0, 1], [1, 2], [2, 0]]), true);
assert.equal(hasCycleDirected(3, [[0, 1], [1, 2]]), false);
assert.equal(hasCycleDirected(1, [[0, 0]]), true); // self-loop

// ── 8. Cycle detection, undirected (parent check)  —  visited neighbor that is not the parent = cycle  —  O(V + E)
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;
}
assert.equal(hasCycleUndirected(3, [[0, 1], [1, 2], [2, 0]]), true);
assert.equal(hasCycleUndirected(3, [[0, 1], [1, 2]]), false);

// ── 9. Topological sort: Kahn's (BFS on in-degree)  —  queue nodes with indegree 0; pop, decrement neighbors  —  O(V + E)
//        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
assert.deepEqual(topoKahn(4, [[0, 1], [0, 2], [1, 3], [2, 3]]), [0, 1, 2, 3]);
assert.deepEqual(topoKahn(2, [[0, 1], [1, 0]]), []);
assert.equal(canFinish(2, [[1, 0]]), true);
assert.equal(canFinish(2, [[1, 0], [0, 1]]), false);

// ── 10. Topological sort: DFS post-order  —  push u after all descendants; reverse at the end  —  O(V + E)
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]]);
assert.ok(t.indexOf(0) < t.indexOf(1) && t.indexOf(1) < t.indexOf(3) && t.indexOf(2) < t.indexOf(3));
assert.deepEqual(topoDFS(2, [[0, 1], [1, 0]]), []);

// ── 11. Dijkstra (non-negative weights)  —  min-heap of [dist, node]; skip stale entries (d > dist[u])  —  O((V + E) log V)
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;
}
assert.deepEqual(dijkstra(4, [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1]], 0), [0, 3, 1, 4]);
assert.deepEqual(dijkstra(2, [], 0), [0, Infinity]);

// ── 12. Bellman-Ford sketch  —  relax ALL edges V-1 times; a V-th improvement means a negative cycle  —  O(VE)
//        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;
}
assert.deepEqual(bellmanFord(3, [[0, 1, 4], [1, 2, -2], [0, 2, 5]], 0), [0, 4, 2]);
assert.equal(bellmanFord(2, [[0, 1, 1], [1, 0, -3]], 0), null);

// ── 13. Union-Find / Disjoint Set Union  —  find with path compression; union by rank  —  ~O(alpha(n)) per op
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);
assert.equal(uf.count, 2);
assert.equal(uf.connected(0, 2), true);
assert.equal(uf.connected(0, 3), false);
assert.equal(uf.union(0, 2), false); // already joined => would be a cycle in an undirected graph

// ── 14. Kruskal's MST  —  sort edges by weight; union-find; take edge if it joins two components  —  O(E log E)
//        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
}
assert.equal(kruskal(4, [[0, 1, 1], [1, 2, 2], [2, 3, 3], [0, 3, 10], [0, 2, 4]]), 6);
assert.equal(kruskal(3, [[0, 1, 1]]), -1);

// ── 15. Bipartite check (2-coloring)  —  BFS; neighbor same color => not bipartite; handle all components  —  O(V + E)
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;
}
assert.equal(isBipartite([[1, 3], [0, 2], [1, 3], [0, 2]]), true);
assert.equal(isBipartite([[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]), false);
assert.equal(isBipartite([[]]), true);

// ── 16. Word ladder (BFS on implicit graph)  —  neighbors = words one letter away; Set for dictionary; count levels  —  O(N * L * 26)
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;
}
assert.equal(ladderLength('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog']), 5);
assert.equal(ladderLength('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log']), 0);
assert.equal(ladderLength('a', 'c', ['a', 'b', 'c']), 2);

console.log('ok: algorithms/graphs.js');