xiv. Directed MST

A minimum spanning arborescence rooted at $r$: every vertex has exactly one incoming edge (except $r$), and all vertices are reachable from $r$. Kruskal and Prim are wrong here. Chu–Liu/Edmonds: take every vertex’s cheapest incoming edge; if they form no cycle, done; otherwise contract a cycle, reduce the weights of edges entering it by the cycle edge they would replace, and recurse. $O(nm)$ simply, $O(m\log m)$ with mergeable heaps (Tarjan/Gabow).

$O(nm)$ version

ll directedMST(int n, int root, vector<array<ll, 3>> E) {     // {u, v, w}; -1 if some vertex is unreachable
    const ll INF = LLONG_MAX / 4; ll res = 0;
    while (true) {
        vector<ll> in(n, INF); vector<int> pre(n, -1);
        for (auto [u, v, w] : E) if (u != v && w < in[v]) in[v] = w, pre[v] = u;
        for (int v = 0; v < n; v++) if (v != root && in[v] == INF) return -1;
        int cnt = 0; vector<int> id(n, -1), vis(n, -1); in[root] = 0;
        for (int v = 0; v < n; v++) {
            res += in[v]; int x = v;
            while (vis[x] != v && id[x] == -1 && x != root) vis[x] = v, x = pre[x];
            if (x != root && id[x] == -1) { for (int y = pre[x]; y != x; y = pre[y]) id[y] = cnt; id[x] = cnt++; }
        }
        if (!cnt) return res;
        for (int v = 0; v < n; v++) if (id[v] == -1) id[v] = cnt++;
        vector<array<ll, 3>> NE;
        for (auto [u, v, w] : E) if (id[u] != id[v]) NE.push_back({id[u], id[v], w - in[v]});
        E = NE; n = cnt; root = id[root];
    }
}

Proof: contraction preserves the optimum

Subtracting a constant $c_v$ from all edges entering $v$ changes every arborescence’s weight by exactly $c_v$ (each has one edge into $v$), so assume every vertex’s cheapest incoming edge has weight 0. If the chosen 0-edges are acyclic they form an arborescence of weight 0, which is optimal since weights are now $\ge 0$. Otherwise let $C$ be a cycle of 0-edges. Claim: some optimal arborescence enters $C$ exactly once. Take an optimal $T$; consider the set of edges of $T$ entering $C$ from outside and keep the one on the tree path from $r$ to $C$ first reached; replace the incoming edges of the other cycle vertices by their cycle edges (weight 0). This doesn’t increase the weight, keeps one incoming edge per vertex, and creates no cycle (every cycle vertex now hangs off the entry vertex along $C$). So optimal arborescences correspond to arborescences of the contracted graph (one entering edge for the super-vertex) plus all cycle edges except the one into the entry vertex, with equal cost under the reduced weights. Each round removes at least one vertex: $O(n)$ rounds of $O(m)$.

$O(m\log m)$ with skew heaps (Tarjan / Gabow)

Each (super)vertex keeps a mergeable heap of incoming edges with a lazy weight shift. Walk from each unvisited vertex along cheapest incoming edges; when the walk closes a cycle, merge the heaps of the cycle (each shifted by its chosen edge’s weight) and continue from the merged super-vertex. Contractions are recorded with a rollback DSU so the actual parent array can be reconstructed.

struct DirectedMST {
    struct E { int a, b; ll w; };
    struct H { E key; int l = 0, r = 0; ll lz = 0; };
    vector<H> t{H{}};
    void push(int x) { if (!x) return; t[x].key.w += t[x].lz; if (t[x].l) t[t[x].l].lz += t[x].lz; if (t[x].r) t[t[x].r].lz += t[x].lz; t[x].lz = 0; }
    int merge(int a, int b) {
        if (!a || !b) return a ^ b;
        push(a); push(b); if (t[a].key.w > t[b].key.w) swap(a, b);
        int m = merge(b, t[a].r); t[a].r = t[a].l; t[a].l = m; return a;
    }
    int pop(int x) { push(x); return merge(t[x].l, t[x].r); }
    struct RUF {
        vector<int> e; vector<pair<int, int>> st; RUF(int n) : e(n, -1) {}
        int find(int x) { return e[x] < 0 ? x : find(e[x]); }
        int time() { return sz(st); }
        void rollback(int tm) { for (int i = time(); i-- > tm;) e[st[i].first] = st[i].second; st.resize(tm); }
        bool join(int a, int b) {
            a = find(a), b = find(b); if (a == b) return false;
            if (e[a] > e[b]) swap(a, b);
            st.push_back({a, e[a]}); st.push_back({b, e[b]}); e[a] += e[b]; e[b] = a; return true;
        }
    };
    pair<ll, vector<int>> solve(int n, int r, const vector<E>& g) {   // {cost, parent} or {-1, {}}
        RUF uf(n); vector<int> heap(n);
        for (auto e : g) { t.push_back(H{e}); heap[e.b] = merge(heap[e.b], sz(t) - 1); }
        ll res = 0; vector<int> seen(n, -1), path(n), par(n); seen[r] = r;
        vector<E> Q(n), in(n, E{-1, -1, 0}); deque<tuple<int, int, vector<E>>> cycs;
        for (int s = 0; s < n; s++) {
            int u = s, qi = 0, w;
            while (seen[u] < 0) {
                if (!heap[u]) return {-1, {}};
                push(heap[u]); E e = t[heap[u]].key;
                t[heap[u]].lz -= e.w; heap[u] = pop(heap[u]);
                Q[qi] = e; path[qi++] = u; seen[u] = s; res += e.w; u = uf.find(e.a);
                if (seen[u] == s) {                         // cycle: contract it
                    int cyc = 0, end = qi, tm = uf.time();
                    do cyc = merge(cyc, heap[w = path[--qi]]); while (uf.join(u, w));
                    u = uf.find(u); heap[u] = cyc; seen[u] = -1;
                    cycs.push_front({u, tm, vector<E>(Q.begin() + qi, Q.begin() + end)});
                }
            }
            for (int i = 0; i < qi; i++) in[uf.find(Q[i].b)] = Q[i];
        }
        for (auto& [u, tm, comp] : cycs) {                  // expand cycles to recover parents
            uf.rollback(tm); E inE = in[u];
            for (auto& e : comp) in[uf.find(e.b)] = e;
            in[uf.find(inE.b)] = inE;
        }
        for (int i = 0; i < n; i++) par[i] = in[i].a;
        return {res, par};
    }
};

Proof sketch: the heap version implements the same contractions

The lazy shift lz -= e.w on a vertex’s heap after choosing its cheapest edge $e$ is exactly “subtract $c_v$ from all edges entering $v$”. Following chosen edges from $s$ either reaches a vertex already settled in this or an earlier walk (no cycle) or closes a cycle among the current walk, which is contracted by merging the shifted heaps; the walk then continues from the super-vertex. Edges inside a contracted cycle have become self-loops; if one surfaces as the cheapest, it forms a cycle of length one: its reduced weight is added to the cost and subtracted from the rest of that heap, which cancels out once the real entering edge is chosen. Each edge is inserted once and popped at most once, and skew-heap merges cost $O(\log m)$ amortised, so the total is $O(m\log m)$. Reconstruction replays contractions in reverse: inside each cycle, every vertex takes its cycle edge except the one entered from outside.

Variants

• Maximum arborescence: negate weights.
• Best root: add a virtual root with an edge of weight $W$ (larger than the sum of all weights) to every vertex; the answer minus $W$ uses exactly one virtual edge, and its target is the optimal root.
• Counting arborescences: directed matrix-tree theorem (Matrix-Tree).
• Minimum arborescence with a degree bound at the root: Aliens trick on the root’s edges.

This models optimal branchings in dependency/precedence graphs generally — task scheduling with directed prerequisites, compiler IR, broadcast trees — anywhere “cheapest way to reach everything from one source, directed” shows up.