Explicações teóricas sobre Grafos aqui
Resumo: Dado a origem, determinar a distância máxima que pode ser alcançada
Explicação: Nos comentários temos a explicação detalhada de cada passo. Mas de forma geral, vamos realizar uma busca em profundidade (DFS), partindo da origem e vamos marcando a distância atual e comparando com a maior que já temos guardada, se essa atual for maior nós guardamos ela.
No final da DFS nós retornamos a distância atual, que é a distância do último vértice explorado, o mais distante da origem.
Obs: DFS significa Depth First Search (Busca Primeiro em Profundidade).
Vamos ao código:
//Autor: Filipe Areias Névola
//Ano: 2008
//Licensa: Você pode usar e alterar, mas deve manter o Autor
#include <stdio.h> //Biblioteca padrão de entrada e saída
#include <string.h>
//número máximo de vértices
#define MAX 151
//vetor de alturas e de distâncias
int alt[MAX], dist[MAX];
//g é a matriz de adjacência que representa o grafo
int g[MAX][MAX];
//número de pontos turísticos
int p;
//Busca Primeiro em Profundidade
int buscaprof(int atual){
//q vai ser o vértice atual e disttemp a distância na volta do backtracking
int q, disttemp;
//se ainda não foi visitado
if (dist[atual] == -1){
//distancia vale 0 pois ele é o atual
dist[atual] = 0;
for (q = 1; q <= p; q++){
//se existe o caminho
if (g[atual][q]){
//começa a explorar esse vértice e dá um passo(soma 1)
disttemp = buscaprof(q) + 1;
//acabaram os vertices por esta caminho confere se essa distancia temporaria é maior que a atual
if (disttemp > dist[atual]){
dist[atual] = disttemp;
}
}
}
}
return dist[atual];
}
//Parte principal do programa
int main(){
/**declarações**/
int i,x,y,l,o,teste=1,v,fim,ini;
/**entrada de dados e processamento**/
while (scanf("%d %d %d", &p, &l, &o)==3&&p){//p==pontos turistico, l==caminhos, o==origem
for (i = 1; i <= p; ++i){
//pega altura dos pontos
scanf("%d", &alt[i]);
}
//zerando a matriz de adjacência, para indicar que ainda não tem arestas
memset(g, 0, sizeof(g));
//vai montar o grafo baseado nas alturas
for (i = 0; i < l; ++i){
scanf("%d %d", &x, &y);
//se é descida
if (alt[x] > alt[y]){
//esse caminho é valido então marca essa aresta
g[x][y]=1;
}
}
//colocando o valor -1 em todas as posições do vetor dist
//para indicar que nenhum vértice foi visitado ainda
memset(dist, -1, sizeof(dist));
//chama a busca para achar a maior distancia e já imprime seu retorno
printf("Teste %d\n%d\n\n", teste++, buscaprof(o));
}
return 0;
}
Alguma dúvida? Pergunte através dos comentários!
Passeio de Bicicleta - SPOJ - 829 PASSEIO
