Solução Uiquipédia

0 Flares Facebook 0 0 Flares ×

Solução por Rogério Júnior

O leitor atento consegue notar facilmente que este é um problema de grafos. Basta vermos cada página como um vértice do grafo, assim, vamos ligar duas página com uma aresta apenas se for possível ir de uma até a outra com um único clique. Se você nunca ouviu falar de grafos, clique aqui para ver a aula introdutória de grafos do Curso Noic. Feita essa análise, é fácil notar que encontrar o menor número de cliques que precisamos para ir de uma página até a outra é o mesmo que encontrar o comprimento do menor caminho que liga duas páginas. Se você nunca resolveu um problema assim, clique aqui para ver a aula do Curso Noic sobre menor caminho em um grafo.No grafo construído, todas as arestas têm peso 1, pois não existe um tipo de clique que custe mais que outro. Logo, como dito na aula, podemos simplesmente usar uma BFS para descobrir o menor caminho entre duas páginas. Se você não conhece esse algoritmo, clique aqui para ver a aula de Flood Fill do Curso Noic.

Assim, basta criarmos um grafo com todos os vértices (páginas) e arestas descritas na entrada (links entre páginas). Feito isso, vamos adicionar também as arestas entre páginas adjacentes na ordem alfabética de todas as páginas da Uiquipédia, pois também é possível acessar páginas vizinhas com um único clique. Para implementarmos tal grafo, é necessária uma estrutura de dados onde possamos salvar frases (string de C++) e acessá-las rapidamente, visto que usaremos uma matriz de adjacência para representarmos o grafo. Desse modo, cada vértice será identificado por um inteiro de 1 até counter (o número de páginas), e precisamos saber, de maneira rápida, qual o número de identificação de uma página apenas pelo seu nome. Para isso, usaremos uma map de nome mapa, onde as chaves serão strings (os nomes das páginas) e os elementos serão inteiros (seus números de identificação). A lista de adjacência será feita com uma matriz de bool, MAXN por MAXN (onde MAXN é número máximo de páginas), de nome tab. Nesse caso, tab[v][u] é true se existe uma aresta que liga o vértice ao vértice u, ou false, caso contrário. Se você não conhece essas estruturas, clique aqui para ver a aula do Curso Noic sobre estruturas do C++.

Desse modo, vamos ler o valor de n, número de links da Uiquipédia, e usaremos um for para, em cada um desses links, declararmos e lermos duas stringspage1 page2, nessa ordem, com o comando "cin >> page1 >> page2;". Feito isso, vamos checar se a página page1 já existe no grafo. Para isso, chamaremos um membro de mapa, a função find(page1), que retornará um ponteiro para a posição page1 de mapa, se ela existir, ou para mapa.end(), caso contrário. Se a página não existir, devemos criá-la, adicionando um ao valor de counter  e salvando que o número da página page1 é counter, com o comando: "if(mapa.find(page1)==mapa.end()) mapa[page1]=++counter;". Repetiremos o mesmo processo com a segunda página. Agora, precisaremos adicionar a aresta que liga page1 page2 (nessa ordem) ao grafo, através do comando "tab[mapa[page1]][mapa[paage2]]=true;".

Depois que lemos a entrada, precisamos adicionar as arestas que ligam páginas vizinhas. Como o map guarda seus elementos em ordem crescente de chave, as páginas estarão salvas em ordem alfabética. Desse modo, basta criarmos dois iterators, it at que representarão uma págian e sua antecessora. Eles começarão com o valor de mapa.begin() e depois usarei o comando it++ para que este se torne um ponteiro para a segunda página. Com um for faremos it percorrer todas as posições de mapa, e ligaremos os vértices salvos em (*it).second e (*at).second com duas arestas, uma que parte do elemento em at e outra que parte do elemento em it. Ao final de cada repetição do for, faço at receber o valor de it, para que ele se torne um ponteiro para o antecessor da próxima página.

Agora, o grafo já está pronto, e basta que eu leia a página de origem e a de destino e imprima a distância entre elas que será calculada com uma BFS. Para isso, basta que salvemos a distância de cada vértice até a origem no vetor dist, que começará com todos os valores iguais a infinito, exceto o da posição da origem, que será zero. Assim, toda vez que formos adicionar um vértice à fila da BFS, salvamos que sua distância à origem é a distância de seu pai somada de 1, e retornarmos a distância até o destino. Segue o código para melhor entendimento:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: