Grafo:
    0 --- 1 --- 3
    |     |
    2 --- 4 --- 5

DFS a partir do vértice 0:

Pilha: [0]                  Visitados: {0}
  Visita 0 → vai para 1
Pilha: [0, 1]               Visitados: {0, 1}
  Visita 1 → vai para 3
Pilha: [0, 1, 3]            Visitados: {0, 1, 3}
  Visita 3 → sem vizinhos não visitados → retrocede
Pilha: [0, 1]
  De 1 → vai para 4
Pilha: [0, 1, 4]            Visitados: {0, 1, 3, 4}
  Visita 4 → vai para 2
Pilha: [0, 1, 4, 2]         Visitados: {0, 1, 3, 4, 2}
  Visita 2 → vizinhos já visitados → retrocede
  De 4 → vai para 5
Pilha: [0, 1, 4, 5]         Visitados: {0, 1, 3, 4, 2, 5}

Ordem: 0 → 1 → 3 → 4 → 2 → 5

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

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

    pub fn init(allocator: Allocator, n: u32) !Grafo {
        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: *Grafo) void {
        for (self.adjacencia) |*l| l.deinit();
        self.allocator.free(self.adjacencia);
    }

    pub fn addAresta(self: *Grafo, u: u32, v: u32) !void {
        try self.adjacencia[u].append(v);
        try self.adjacencia[v].append(u);
    }

    pub fn addArestaDirecionada(self: *Grafo, u: u32, v: u32) !void {
        try self.adjacencia[u].append(v);
    }
};

/// DFS recursiva — retorna a ordem de visita.
pub fn dfsRecursiva(
    allocator: Allocator,
    grafo: *const Grafo,
    origem: u32,
) ![]u32 {
    const visitado = try allocator.alloc(bool, grafo.num_vertices);
    defer allocator.free(visitado);
    @memset(visitado, false);

    var ordem = std.ArrayList(u32).init(allocator);
    dfsHelper(grafo, origem, visitado, &ordem) catch {};
    return ordem.toOwnedSlice();
}

fn dfsHelper(
    grafo: *const Grafo,
    v: u32,
    visitado: []bool,
    ordem: *std.ArrayList(u32),
) !void {
    visitado[v] = true;
    try ordem.append(v);

    for (grafo.adjacencia[v].items) |vizinho| {
        if (!visitado[vizinho]) {
            try dfsHelper(grafo, vizinho, visitado, ordem);
        }
    }
}

/// DFS iterativa usando pilha explícita (evita stack overflow).
pub fn dfsIterativa(
    allocator: Allocator,
    grafo: *const Grafo,
    origem: u32,
) ![]u32 {
    const visitado = try allocator.alloc(bool, grafo.num_vertices);
    defer allocator.free(visitado);
    @memset(visitado, false);

    var ordem = std.ArrayList(u32).init(allocator);
    var pilha = std.ArrayList(u32).init(allocator);
    defer pilha.deinit();

    try pilha.append(origem);

    while (pilha.items.len > 0) {
        const v = pilha.pop();
        if (visitado[v]) continue;

        visitado[v] = true;
        try ordem.append(v);

        // Adiciona vizinhos na pilha (em ordem reversa para manter ordem)
        var i: usize = grafo.adjacencia[v].items.len;
        while (i > 0) {
            i -= 1;
            const vizinho = grafo.adjacencia[v].items[i];
            if (!visitado[vizinho]) {
                try pilha.append(vizinho);
            }
        }
    }

    return ordem.toOwnedSlice();
}

/// DFS com timestamps (tempo de descoberta e finalização).
/// Útil para detecção de ciclos e ordenação topológica.
pub fn dfsComTimestamps(
    allocator: Allocator,
    grafo: *const Grafo,
) !struct { descoberta: []u32, finalizacao: []u32, tem_ciclo: bool } {
    const n = grafo.num_vertices;

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

    const descoberta = try allocator.alloc(u32, n);
    const finalizacao = try allocator.alloc(u32, n);
    var tempo: u32 = 0;
    var tem_ciclo = false;

    var v: u32 = 0;
    while (v < n) : (v += 1) {
        if (cor[v] == 0) {
            dfsTimestampHelper(grafo, v, cor, descoberta, finalizacao, &tempo, &tem_ciclo);
        }
    }

    return .{ .descoberta = descoberta, .finalizacao = finalizacao, .tem_ciclo = tem_ciclo };
}

fn dfsTimestampHelper(
    grafo: *const Grafo,
    v: u32,
    cor: []u8,
    descoberta: []u32,
    finalizacao: []u32,
    tempo: *u32,
    tem_ciclo: *bool,
) void {
    cor[v] = 1; // cinza
    descoberta[v] = tempo.*;
    tempo.* += 1;

    for (grafo.adjacencia[v].items) |vizinho| {
        if (cor[vizinho] == 0) {
            dfsTimestampHelper(grafo, vizinho, cor, descoberta, finalizacao, tempo, tem_ciclo);
        } else if (cor[vizinho] == 1) {
            tem_ciclo.* = true; // aresta para vértice cinza = ciclo
        }
    }

    cor[v] = 2; // preto
    finalizacao[v] = tempo.*;
    tempo.* += 1;
}

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

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

    // DFS recursiva
    const ordem_rec = try dfsRecursiva(allocator, &grafo, 0);
    defer allocator.free(ordem_rec);
    try stdout.print("DFS recursiva: ", .{});
    for (ordem_rec) |v| try stdout.print("{d} ", .{v});
    try stdout.print("\n", .{});

    // DFS iterativa
    const ordem_iter = try dfsIterativa(allocator, &grafo, 0);
    defer allocator.free(ordem_iter);
    try stdout.print("DFS iterativa: ", .{});
    for (ordem_iter) |v| try stdout.print("{d} ", .{v});
    try stdout.print("\n", .{});
}