Grafo:
  A --4-- B --8-- C
  |      /|      |
  8    2  7     2
  |  /    |    /
  D --9-- E --4-- F
        1-|
          G

Prim a partir de A:
  MST = {A}
  1. Menor aresta: A-B(4) → MST = {A, B}
  2. Menor aresta: B-D(2) → MST = {A, B, D}
  3. Menor aresta: A-D? Não, já na MST. B-E(7)? D-E(9)?
     B-C(8)? Menor: B-E(7) → MST = {A, B, D, E}
  4. Menor: E-G(1) → MST = {A, B, D, E, G}
  5. Menor: E-F(4) ou C-F(2)? E-C? C-F(2) via E→C
     Menor: C-F(2) hmm... E-F(4). Menor de fora: C(8), F(4)
     Menor: E-F(4) → MST = {A, B, D, E, G, F}
  6. Menor: F-C(2) → MST = {A, B, D, E, G, F, C}

  Peso total = 4 + 2 + 7 + 1 + 4 + 2 = 20

const std = @import("std");
const Allocator = std.mem.Allocator;
const Order = std.math.Order;

const Aresta = struct {
    destino: u32,
    peso: i64,
};

const GrafoPonderado = struct {
    adjacencia: []std.ArrayList(Aresta),
    num_vertices: u32,
    allocator: Allocator,

    pub fn init(allocator: Allocator, n: u32) !GrafoPonderado {
        const adj = try allocator.alloc(std.ArrayList(Aresta), n);
        for (adj) |*lista| lista.* = std.ArrayList(Aresta).init(allocator);
        return .{ .adjacencia = adj, .num_vertices = n, .allocator = allocator };
    }

    pub fn deinit(self: *GrafoPonderado) void {
        for (self.adjacencia) |*l| l.deinit();
        self.allocator.free(self.adjacencia);
    }

    pub fn addAresta(self: *GrafoPonderado, u: u32, v: u32, peso: i64) !void {
        try self.adjacencia[u].append(.{ .destino = v, .peso = peso });
        try self.adjacencia[v].append(.{ .destino = u, .peso = peso });
    }
};

const NoHeap = struct {
    vertice: u32,
    peso: i64,

    fn comparar(_: void, a: NoHeap, b: NoHeap) Order {
        return std.math.order(a.peso, b.peso);
    }
};

/// Algoritmo de Prim — retorna arestas da MST e peso total.
pub fn prim(
    allocator: Allocator,
    grafo: *const GrafoPonderado,
) !struct { pai: []i32, chave: []i64, peso_total: i64 } {
    const n = grafo.num_vertices;
    const INF: i64 = std.math.maxInt(i64);

    const chave = try allocator.alloc(i64, n);
    @memset(chave, INF);

    const pai = try allocator.alloc(i32, n);
    @memset(pai, -1);

    const na_mst = try allocator.alloc(bool, n);
    defer allocator.free(na_mst);
    @memset(na_mst, false);

    var heap = std.PriorityQueue(NoHeap, void, NoHeap.comparar).init(allocator, {});
    defer heap.deinit();

    // Começa pelo vértice 0
    chave[0] = 0;
    try heap.add(.{ .vertice = 0, .peso = 0 });

    var peso_total: i64 = 0;

    while (heap.removeOrNull()) |no| {
        const u = no.vertice;
        if (na_mst[u]) continue;
        na_mst[u] = true;
        peso_total += no.peso;

        for (grafo.adjacencia[u].items) |aresta| {
            const v = aresta.destino;
            if (!na_mst[v] and aresta.peso < chave[v]) {
                chave[v] = aresta.peso;
                pai[v] = @intCast(u);
                try heap.add(.{ .vertice = v, .peso = aresta.peso });
            }
        }
    }

    return .{ .pai = pai, .chave = chave, .peso_total = peso_total };
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var grafo = try GrafoPonderado.init(allocator, 5);
    defer grafo.deinit();

    try grafo.addAresta(0, 1, 4);
    try grafo.addAresta(0, 3, 8);
    try grafo.addAresta(1, 2, 6);
    try grafo.addAresta(1, 3, 2);
    try grafo.addAresta(2, 3, 5);
    try grafo.addAresta(2, 4, 3);
    try grafo.addAresta(3, 4, 9);

    const res = try prim(allocator, &grafo);
    defer allocator.free(res.pai);
    defer allocator.free(res.chave);

    try stdout.print("Árvore Geradora Mínima (Prim):\n", .{});
    for (res.pai, 0..) |p, i| {
        if (p != -1) {
            try stdout.print("  {d} --- {d}  (peso: {d})\n", .{ p, i, res.chave[i] });
        }
    }
    try stdout.print("Peso total: {d}\n", .{res.peso_total});
}