Uiquipédia

uiqui.cpp

#include <map>
#include <queue>
#include <string>
#include <iostream>

using namespace std;

#define MAXN 2020
#define INF 999999999

int n, counter;

bool tab[MAXN][MAXN]; // grafo
int dist[MAXN]; // array para a bfs

map<string, int> mapa; // guarda o número de identificação de cada página

// função bfs, que recebe as páginas de origem e destino como parâmetros
int bfs(int ori, int dest){
	
	// infinito as distâncias à ori, e faço com que a distância de ori a ori seja zero
	for(int i=1; i<=counter; i++) dist[i]=INF; dist[ori]=0;
	
	// declaro a fila da BFS e coloco nela o vértice ori
	queue<int> fila; fila.push(ori);
	
	// enquanto a pilha não estiver vazia
	while(!fila.empty()){
		
		// v será o primeiro vértice na fila
		int v=fila.front(); fila.pop(); // e retiro o vértice da frente
		
		// para cada um dos vértices do grafo
		for(int u=0; u<=counter; u++){
			
			// se existe uma aresta entre ele e v, e ele ainda não foi marcado
			if(tab[v][u] and dist[u]==INF){
				
				// salvo que sua distância à ori é a distância de v somada de 1
				dist[u]=dist[v]+1;
				fila.push(u); // e o adiciono à fila da BFS
			}
		}			
	}
	
	// no fim, a função retorna a distância de dest até a origem
	return dist[dest];
}

int main(){
	
	cin >> n; // leio o número de links
		
	for(int i=1; i<=n; i++){ // para cada link
		
		// declaro e leio as páginas linkadas por ele
		string page1, page2;
		cin >> page1 >> page2;
		
		// adiciono ao grafo as páginas que ainda não existem nele
		if(mapa.find(page1)==mapa.end()) mapa[page1]=++counter;
		if(mapa.find(page2)==mapa.end()) mapa[page2]=++counter;
		
		// e represento o link entre page1 e page2 com uma aresta direcionada no grafo
		tab[mapa[page1]][mapa[page2]]=true;
	}
	
	// declaro os iteradores it e at apontando para o começo de mapa
	map<string,int>::iterator it=mapa.begin(), at=mapa.begin();
	
	it++; // e faço it reeceber o próximo elemento de mapa
	
	for(; it!=mapa.end(); it++){ // percorro mapa com it
		
		// e crio uma aresta bidirecional entre páginas vizinhas
		tab[(*it).second][(*at).second]=tab[(*at).second][(*it).second]=true;
		at=it; // e faço at receber o próximo elemento de mapa
	}
	
	// declaro e leio as páginas de origem e destino da busca
	string page_ori, page_dest;
	cin >> page_ori >> page_dest;
	
	// e imprimo a distância entre elas através de uma BFS, seguida da quebra de linha
	cout << bfs(mapa[page_ori], mapa[page_dest]) << endl;
	
	return 0;
}