Minimum Spanning Tree

// ─── Kruskal's (sort edges + Union-Find) ───────────────────────────────────
function kruskal(n, edges) { // edges = [[weight, u, v], ...]
    edges.sort((a, b) => a[0] - b[0]);
    const parent = Array.from({length: n}, (_, i) => i);
    const rank = new Array(n).fill(0);
    function find(x) {
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    }
    function union(x, y) {
        const [px, py] = [find(x), find(y)];
        if (px === py) return false;
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[px] > rank[py]) parent[py] = px;
        else { parent[py] = px; rank[px]++; }
        return true;
    }
    let totalWeight = 0, edgesUsed = 0;
    for (const [w, u, v] of edges) {
        if (union(u, v)) { totalWeight += w; edgesUsed++; }
        if (edgesUsed === n - 1) break;
    }
    return edgesUsed === n - 1 ? totalWeight : -1; // -1 if graph disconnected
}

// ─── Prim's (min-heap, grow from node 0) ────────────────────────────────────
function prim(n, adjList) { // adjList[u] = [[weight, v], ...]
    const inMST = new Array(n).fill(false);
    const heap = [[0, 0]]; // [cost, node], min-heap
    let totalWeight = 0, count = 0;
    while (heap.length && count < n) {
        const [cost, node] = heap.shift(); // use actual min-heap in prod
        if (inMST[node]) continue;
        inMST[node] = true; totalWeight += cost; count++;
        for (const [w, nei] of adjList[node]) {
            if (!inMST[nei]) heap.push([w, nei]);
        }
        heap.sort((a, b) => a[0] - b[0]); // use priority queue in production
    }
    return count === n ? totalWeight : -1;
}