Graphs

// 1) Adjacency list — best for sparse graphs
class Graph {
    constructor() { this.adj = new Map(); }
    addEdge(u, v, w = 1) {
        if (!this.adj.has(u)) this.adj.set(u, []);
        if (!this.adj.has(v)) this.adj.set(v, []);
        this.adj.get(u).push([v, w]);
        this.adj.get(v).push([u, w]);   // remove this line for directed
    }
}

// 2) BFS — shortest path on an unweighted graph
function bfs(g, start) {
    const dist = new Map([[start, 0]]);
    const q = [start];
    while (q.length) {
        const u = q.shift();
        for (const [v] of g.adj.get(u) ?? []) {
            if (dist.has(v)) continue;
            dist.set(v, dist.get(u) + 1);
            q.push(v);
        }
    }
    return dist;
}

// 3) DFS — recursion or explicit stack
function dfs(g, start, visited = new Set()) {
    visited.add(start);
    for (const [v] of g.adj.get(start) ?? []) {
        if (!visited.has(v)) dfs(g, v, visited);
    }
    return visited;
}

// 4) Dijkstra — shortest path with non-negative weights, with a min-heap
function dijkstra(g, start) {
    const dist = new Map();
    for (const u of g.adj.keys()) dist.set(u, Infinity);
    dist.set(start, 0);

    // tiny binary heap of [dist, node]
    const heap = [[0, start]];
    while (heap.length) {
        heap.sort((a, b) => a[0] - b[0]);
        const [d, u] = heap.shift();
        if (d > dist.get(u)) continue;
        for (const [v, w] of g.adj.get(u) ?? []) {
            const nd = d + w;
            if (nd < dist.get(v)) {
                dist.set(v, nd);
                heap.push([nd, v]);
            }
        }
    }
    return dist;
}

// 5) Topological sort — DAG order (Kahn's algorithm)
function topo(g) {
    const indeg = new Map();
    for (const u of g.adj.keys()) indeg.set(u, 0);
    for (const list of g.adj.values()) for (const [v] of list) indeg.set(v, (indeg.get(v) ?? 0) + 1);

    const q = [...indeg].filter(([, d]) => d === 0).map(([u]) => u);
    const out = [];
    while (q.length) {
        const u = q.shift();
        out.push(u);
        for (const [v] of g.adj.get(u) ?? []) {
            indeg.set(v, indeg.get(v) - 1);
            if (indeg.get(v) === 0) q.push(v);
        }
    }
    return out.length === g.adj.size ? out : null;   // null = cycle
}

// Adjacency list — cleanest for sparse graphs.
const g = new Map();
for (const [u, v] of edges) {
    if (!g.has(u)) g.set(u, []);
    g.get(u).push(v);
}