Algoritmos de Grafos para Programação Competitiva

A Pressão do Relógio

Na Olimpíada Brasileira de Informática (OBI), 3 horas separam o ouro do nada. Cada segundo de execução importa. Cada decisão de estrutura de dados pode ser a diferença entre "Accepted" e o temido TLE — Time Limit Exceeded.

Este post documenta os 16 arquivos e 10 problemas que resolvi nas edições de 2019, 2021 e 2023 da OBI — e os algoritmos de grafos que construí para treinar. O resultado? Medalha de bronze na OBI 2024.

Bellman-Ford: O Relaxamento Massivo

Quando precisas de caminho mínimo mas o grafo tem pesos negativos, Dijkstra não serve. Bellman-Ford relaxa todas as arestas V-1 vezes — bruto, mas correto.

A implementação suporta 3 representações de grafo (classe OOP completa com Node, parent, distance):

class Node:
    def __init__(self, tag):
        self.tag = tag
        self.parent = None
        self.distance = float('inf')

    def __lt__(self, other):
        return self.distance < other.distance

class BellmanFord:
    def __init__(self, vertices, edges):
        self.V = vertices
        self.edges = edges  # dict: (u,v) -> weight
        self.nodes = [Node(i) for i in range(vertices)]

    def relax(self, u, v, weight):
        if self.nodes[u].distance + weight < self.nodes[v].distance:
            self.nodes[v].distance = self.nodes[u].distance + weight
            self.nodes[v].parent = u
            return True
        return False

    def run(self, source):
        self.nodes[source].distance = 0

        # V-1 relaxamentos
        for _ in range(self.V - 1):
            for (u, v), w in self.edges.items():
                self.relax(u, v, w)

        # Detecção de ciclo negativo (iteração extra)
        for (u, v), w in self.edges.items():
            if self.nodes[u].distance + w < self.nodes[v].distance:
                raise Exception("Ciclo negativo detectado!")

        return self.nodes

Dijkstra: O Algoritmo Guloso (3 Variantes)

A dor de implementar Dijkstra três vezes em formatos diferentes me ensinou como cada representação de grafo afeta a performance:

Variante 1: Matriz de Adjacência

# O(V²) — mais lento, mas simples
def dijkstra_matrix(graph, start, V):
    dist = [float('inf')] * V
    dist[start] = 0
    visited = [False] * V
    parents = [None] * V

    for _ in range(V):
        # Seleciona vértice não-visitado com menor distância
        u = min_distance(dist, visited, V)
        visited[u] = True

        for v in range(V):
            if graph[u][v] > 0 and not visited[v]:
                if dist[u] + graph[u][v] < dist[v]:
                    dist[v] = dist[u] + graph[u][v]
                    parents[v] = u

    return dist, parents

Variante 2: Lista de Adjacência

# Mais eficiente em grafos esparsos
def dijkstra_adj_list(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    parents = {start: None}
    visited = set()

    while len(visited) < len(graph):
        u = min((d, n) for n, d in dist.items()
                if n not in visited)[1]
        visited.add(u)

        for v, w in graph[u]:
            if v not in visited and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parents[v] = u

    return dist, parents

Variante 3: Lista de Arestas com heapq

import heapq

def dijkstra_heap(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    parents = {start: None}
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                parents[v] = u
                heapq.heappush(pq, (nd, v))

    return dist, parents

A reconstrução do caminho usa o array parents[]:

def show_path(parents, target):
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = parents.get(node)
    return list(reversed(path))

Problemas OBI: As Trincheiras

OBI 2019 — Soma (A Dor da Força Bruta)

O problema clássico: encontrar pares de números que somam a um valor alvo. A primeira intuição? Dois loops.

# O(N³) — TLE garantido para N > 1.000
for i in range(n):
    for j in range(i+1, n):
        if sum(arr[i:j+1]) == target:  # sum() é O(N) extra!
            count += 1

A solução passava por eliminar o sum() interno e usar acumuladores — ou melhor, sets para busca O(1). Lição: quando vês N ≤ 10⁵ no enunciado, não penses em O(N²).

OBI 2019 — Chuva (Propagação em Grade)

Simulação de propagação de água numa matriz 2D. A sacada: em vez de BFS/DFS (que são O(N²) em matrizes), usar varreduras direcionais — uma passagem esquerda→direita e outra direita→esquerda. Complexidade real: O(N × M) por passagem.

OBI 2021 — Tempo (Dicionários como Máquina de Estado)

Simulação de um sistema de controle temporal com eventos R (registrar), E (encerrar), T (total). A estrutura core: um dicionário mapeando nomes para pares [acumulador, estado]:

registros = {}  # nome -> [tempo_acumulado, estado_ativo]

for evento in eventos:
    tipo, nome, tempo = parse(evento)
    if tipo == 'R':
        if nome not in registros:
            registros[nome] = [0, True]
        registros[nome][1] = True
    elif tipo == 'E':
        registros[nome][0] += tempo
        registros[nome][1] = False
    elif tipo == 'T':
        for k in sorted(registros):
            print(k, registros[k][0])

OBI 2021 — Cifra (Manipulação de Strings)

Cifra de substituição onde cada consoante é mapeada pela vogal mais próxima no alfabeto. Implementação pura de indexação e distância absoluta — sem regex, sem bibliotecas.

OBI 2023 — Contas (Algoritmo Guloso)

Maximizar o número de contas pagas com orçamento limitado. A solução gulosa clássica: ordena por valor crescente e paga as baratas primeiro.

# O(N log N) — sort domina
contas.sort()
total = 0
pagas = 0
for conta in contas:
    if total + conta <= orcamento:
        total += conta
        pagas += 1
    else:
        break

OBI 2023 — Leilão (Ordenação com Lambda)

Encontrar o maior lance num leilão. Uso de sort(key=lambda, reverse=True) em lista de tuplas (nome, valor):

lances = [(nome, valor) for _ in range(n)]
lances.sort(key=lambda x: x[1], reverse=True)
print(lances[0][0])  # Nome do vencedor

O Benchmark: Listas vs. Dicionários

O arquivo exec.py existe para provar um ponto sobre otimização. Usando o módulo timeit:

import timeit

# list.sort() — ordena in-place
list_time = timeit.timeit(
    'data.sort()',
    setup='data = list(range(10000, 0, -1))',
    number=1000
)

# sorted(dict) com lambda — cria nova lista
dict_time = timeit.timeit(
    'sorted(d.items(), key=lambda x: x[1])',
    setup='d = {i: 10000-i for i in range(10000)}',
    number=1000
)

print(f"List:  {list_time:.4f}s")
print(f"Dict:  {dict_time:.4f}s")
# Spoiler: list.sort() é MUITO mais rápido

Na OBI, milissegundos decidem entre Accepted e TLE. A estrutura de dados que escolhes dita quem ganha a medalha.

Resumo dos Problemas

5 Lições da OBI

1. Lê as restrições: N ≤ 10⁵ → O(N log N) no máximo. N ≤ 10³ → O(N²) ok
2. Domine as estruturas: Fila, pilha, heap, set, dict — são mais importantes que algoritmos
3. Teste com extremos: Grafos vazios, um nó, ciclos negativos, strings vazias
4. Não otimizes prematuramente: Faz funcionar primeiro, depois mede com timeit
5. Reconhece padrões: Quando o enunciado diz "menor caminho", pensa automatico "BFS ou Dijkstra?"