Roteiro 5

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

< Voltar para: Roteiros | Roteiro 4

Introdução

A Teoria dos Grafos é extremamente importante em Ciência da Computação, pois tem inúmeras aplicações. O mesmo acontece em competições: em uma prova da Maratona, sempre haverá um problema a ser resolvido usando grafos. O objetivo deste roteiro é introduzir a teoria dos grafos, ensinando os algoritmos fundamentais em grafos: as buscas.

Materiais de Apoio

Os materiais do wikipedia são apenas para aprender os conceitos básicos. O tutorial do TopCoder é o melhor e abrange tanto este roteiro quanto o próximo. O último tutorial apresenta o algoritmo de Ordenação Topológica.

Problemas

Lista de problemas para serem resolvidos. A solução está disponível, mas recomendamos que não a consulte antes de muito trabalho e implementação. Também é recomendável que resolva o aquecimento (rosa) primeiro.

Roteiro 5
# Problema Link Online Judge Nível
1 IREVIR Ir e vir SPOJ-BR 2
2 ENERGIA Transmissão de Energia SPOJ-BR 2
3 MESA Mesa da Sra Montagny! SPOJ-BR 2
4 PEDAGIO Pedágio SPOJ-BR 2
5 NUMERDOS Número de Erdos SPOJ-BR 2
6 DENGUE Dengue SPOJ-BR 2
7 DUENDE Duende Perdido SPOJ-BR 2
8 NATUREZA Natureza SPOJ-BR 2
9 ORKUT Orkut SPOJ-BR 2
10 UVa 11060 Beverages UVa 2
11 URI1469 Boss URI 2
12 Distance in Tree Distance in Tree Codeforces 3
13 Cthulhu Cthulhu Codeforces 3

Próximo Roteiro

O próximo roteiro de treinamento tratará de problemas de Caminho Mínimo e Árvore Geradora Mínima em Teoria dos Grafos. Recomendamos que você avance apenas depois de ler todo o material de apoio e ter feito, pelo menos, 6 problemas incluindo os 3 em negrito.

Link para o Roteiro 6

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas