DAG de dependências:
  5 → 0    4 → 0    4 → 1    2 → 3    3 → 1    5 → 2

     5 ----→ 0 ←---- 4
     |                |
     ↓                ↓
     2 ---→ 3 ---→ 1

Grau de entrada: [2, 2, 1, 1, 0, 0]
Vértices com grau 0: {4, 5}

Passo 1: remove 4 → grau de [0,1] diminui → 0:[1], 1:[1]
Passo 2: remove 5 → grau de [0,2] diminui → 0:[0], 2:[0]
Passo 3: remove 0 (grau 0 agora)
Passo 4: remove 2 → 3:[0]
Passo 5: remove 3 → 1:[0]
Passo 6: remove 1

Resultado: [4, 5, 0, 2, 3, 1] ou [5, 4, 2, 0, 3, 1] ...
(Pode haver múltiplas ordenações válidas)

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

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

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

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

    pub fn addAresta(self: *GrafoDirecionado, de: u32, para: u32) !void {
        try self.adjacencia[de].append(para);
    }
};

/// Ordenação Topológica usando o algoritmo de Kahn (BFS).
/// Retorna null se o grafo contiver ciclo.
pub fn kahnTopologicalSort(
    allocator: Allocator,
    grafo: *const GrafoDirecionado,
) !?[]u32 {
    const n = grafo.num_vertices;

    // Calcula grau de entrada
    const grau_entrada = try allocator.alloc(u32, n);
    defer allocator.free(grau_entrada);
    @memset(grau_entrada, 0);

    for (grafo.adjacencia) |lista| {
        for (lista.items) |v| {
            grau_entrada[v] += 1;
        }
    }

    // Fila com vértices de grau de entrada 0
    var fila = std.ArrayList(u32).init(allocator);
    defer fila.deinit();

    var i: u32 = 0;
    while (i < n) : (i += 1) {
        if (grau_entrada[i] == 0) try fila.append(i);
    }

    var resultado = std.ArrayList(u32).init(allocator);

    while (fila.items.len > 0) {
        const v = fila.orderedRemove(0);
        try resultado.append(v);

        for (grafo.adjacencia[v].items) |vizinho| {
            grau_entrada[vizinho] -= 1;
            if (grau_entrada[vizinho] == 0) {
                try fila.append(vizinho);
            }
        }
    }

    // Se não processou todos os vértices, há ciclo
    if (resultado.items.len != n) {
        resultado.deinit();
        return null;
    }

    return try resultado.toOwnedSlice();
}

/// Ordenação Topológica usando DFS.
pub fn dfsTopologicalSort(
    allocator: Allocator,
    grafo: *const GrafoDirecionado,
) !?[]u32 {
    const n = grafo.num_vertices;

    // 0=branco, 1=cinza, 2=preto
    const cor = try allocator.alloc(u8, n);
    defer allocator.free(cor);
    @memset(cor, 0);

    var pilha = std.ArrayList(u32).init(allocator);
    var tem_ciclo = false;

    var v: u32 = 0;
    while (v < n) : (v += 1) {
        if (cor[v] == 0) {
            dfsTopoHelper(grafo, v, cor, &pilha, &tem_ciclo) catch {};
        }
    }

    if (tem_ciclo) {
        pilha.deinit();
        return null;
    }

    // Inverte a pilha para obter a ordenação
    const resultado = try pilha.toOwnedSlice();
    std.mem.reverse(u32, resultado);
    return resultado;
}

fn dfsTopoHelper(
    grafo: *const GrafoDirecionado,
    v: u32,
    cor: []u8,
    pilha: *std.ArrayList(u32),
    tem_ciclo: *bool,
) !void {
    cor[v] = 1; // cinza

    for (grafo.adjacencia[v].items) |vizinho| {
        if (cor[vizinho] == 1) {
            tem_ciclo.* = true;
            return;
        }
        if (cor[vizinho] == 0) {
            try dfsTopoHelper(grafo, vizinho, cor, pilha, tem_ciclo);
        }
    }

    cor[v] = 2; // preto
    try pilha.append(v);
}

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 GrafoDirecionado.init(allocator, 6);
    defer grafo.deinit();

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

    // Kahn
    if (try kahnTopologicalSort(allocator, &grafo)) |ordem| {
        defer allocator.free(ordem);
        try stdout.print("Kahn: ", .{});
        for (ordem) |v| try stdout.print("{d} ", .{v});
        try stdout.print("\n", .{});
    } else {
        try stdout.print("Ciclo detectado!\n", .{});
    }

    // DFS
    if (try dfsTopologicalSort(allocator, &grafo)) |ordem| {
        defer allocator.free(ordem);
        try stdout.print("DFS:  ", .{});
        for (ordem) |v| try stdout.print("{d} ", .{v});
        try stdout.print("\n", .{});
    }
}