Categoria: Grafos (DFS)

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