O algoritmo DFS (Busca em Profundidade) é frequentemente utilizado em competições como a Blue Cup, especialmente para problemas de alocação e navegação em grafos/trees. Aqui, discutiremos dois tipos principais de problemas que envolvem DFS.

Tipo Um: DFS para Processos de Alocação

Exemplo 1: Pouso de Aviões

Descrição do Problema:

N aviões estão prontos para pousar em um aeroporto com uma única pista de pouso. Cada avião i chega ao aeroporto no momento Ti e pode esperar até Di momentos antes de precisar pousar, levando Li momentos para completar o procedimento de pouso. Os aviões podem pousar imediatamente após o anterior, mas não podem iniciar o procedimento enquanto outro está em andamento. Determinar se todos os aviões podem pousar com segurança.

Formato de Entrada:

A entrada contém múltiplos conjuntos de dados. A primeira linha contém um inteiro T, indicando o número de conjnutos de teste. Para cada conjunto de dados, a prmieira linha contém um inteiro N. As próximas N linhas contêm três inteiros: Ti, Di e Li.

Formato de Saída:

Para cada conjunto de dados, imprimir "SIM" ou "NAO", indicando se todos os aviões podem pousar com segurança.

Código Exemplo:

def explorar(avioes, pousaram, total_avioes, tempo_atual, avioes_pousados):
    if avioes_pousados == total_avioes:
        return True
    for i in range(total_avioes):
        if pousaram[i]:
            continue
        if avioes[i][1] < tempo_atual:
            return False
        pousaram[i] = True
        if explorar(avioes, pousaram, total_avioes, max(tempo_atual, avioes[i][0]) + avioes[i][2], avioes_pousados + 1):
            return True
        pousaram[i] = False
    return False

casos_teste = int(input())
for _ in range(casos_teste):
    n = int(input())
    avioes = []
    for _ in range(n):
        a, b, c = map(int, input().split())
        avioes.append((a, a + b, c))
    pousaram = [False] * n
    if explorar(avioes, pousaram, n, 0, 0):
        print("SIM")
    else:
        print("NAO")

Exemplo 2: Distribuição de Doces

Descrição do Problema:

Há dois tipos de doces, com 9 e 16 unidades respectivamente, a serem distribuídos entre 7 crianças, onde cada criança deve receber entre 2 e 5 doces no total. Calcular quantas maneiras diferentes existem de distribuir todos os doces.

Solução:

A chave é evitar contar soluções repetidas. Utilizamos recursão para distribuir os doces entre as crianças.

Código Exemplo:

def distribuir_doces(indice, doce1, doce2):
    global contagem
    if indice >= 8:
        if doce1 == 0 and doce2 == 0:
            contagem += 1
        return
    for i in range(doce1 + 1):
        for j in range(doce2 + 1):
            if 2 <= i + j <= 5:
                distribuir_doces(indice + 1, doce1 - i, doce2 - j)

contagem = 0
distribuir_doces(1, 9, 16)
print(contagem)

Tipo Dois: DFS em Árvores

Exemplo 1: Guia Turístico

Descrição do Problema:

Um parque turístico possui N pontos de interesse conectados por N-1 estradas formando uma árvore. Um guia deve levar turistas por K dessses pontos em uma ordem específica, mas pode omitir um ponto. Calcular o tempo total necessário para visitar K-1 pontos para cada ponto omitido.

Entrada:

A primeira linha contém N e K. As próximas N-1 linhas descrevem as estradas e seus tempos de percurso. A última linha lista os K pontos de interesse na ordem de visita.

Saída:

K tempos totais, um para cada ponto omitido.

Código Exemplo:

def caminhar(inicio, fim, atual, anterior, custo_total):
    global arestas
    global pesos
    if atual == fim:
        return custo_total
    for i, (destino, peso) in enumerate(arestas[atual]):
        if destino == anterior:
            continue
        temp = caminhar(inicio, fim, destino, atual, custo_total + pesos[inicio][fim][i])
        if temp > 0:
            return temp
    return 0

n, k = map(int, input().split())
arestas = [[] for _ in range(n + 1)]
pesos = [[{} for _ in range(n + 1)] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v, t = map(int, input().split())
    arestas[u].append((v, t))
    arestas[v].append((u, t))
    pesos[u][v][v] = t
    pesos[v][u][u] = t
itinerario = list(map(int, input().split()))
total_custo = 0
custos_parciais = [0] * (k - 1)
for i in range(1, k):
    custos_parciais[i - 1] = caminhar(itinerario[i - 1], itinerario[i], itinerario[i - 1], -1, 0)
    total_custo += custos_parciais[i - 1]
print(total_custo - custos_parciais[0], end=' ')
for i in range(1, k - 1):
    print(total_custo - custos_parciais[i - 1] - custos_parciais[i] + caminhar(itinerario[i - 1], itinerario[i + 1], itinerario[i - 1], -1, 0), end=' ')
print(total_custo - custos_parciais[k - 2], end=' ')