Curso 2023/2024
En este ejercicio podemos aplicar un razonamiento que hemos visto en el ejercicio 3.c del tema 6: movernos utilizando arcos de entrada.
El problema se resuelve eficientemente haciendo una búsqueda en anchura desde el vértice t que recorra los arcos de entrada, y añadiendo los jugadores al resultado en el orden en que los vamos encontrando en esa búsqueda. De ese modo, quedan ordenados de menor a mayor distancia a t.
El coste temporal y espacial de este algoritmo es O(n + |V| + |E|) gracias a que trabajamos con una representación del grafo mediante listas de adyacencia.
void GrafoDirigido::rankingPorDistanciaAlObjetivo(int t, vector<int> & jugadores) const { // Empezamos asociando a cada vertice un contador con la cantidad de jugadores en ese vertice vector<int> jugadoresEnVertice(vertices.size(), 0); for (int v : jugadores) jugadoresEnVertice[v]++; // Tratamos el caso especial de que haya jugadores en el vertice t int contador = 0; for (int i = jugadoresEnVertice[t]; i > 0; i--) jugadores[contador++] = t; if (contador == jugadores.size()) return; // Realizamos una busqueda en anchura desde t siguiendo los arcos de entrada, // y ponemos los jugadores en el resultado en el orden en que los vamos encontrando vector<bool> visitado(vertices.size(), false); queue<int> cola; visitado[t] = true; cola.push(t); while (! cola.empty()) { int v = cola.front(); cola.pop(); for (Arco * arco = vertices[v].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente) if (! visitado[arco->vecino]) { for (int i = jugadoresEnVertice[arco->vecino]; i > 0; i--) jugadores[contador++] = arco->vecino; if (contador == jugadores.size()) return; visitado[arco->vecino] = true; cola.push(arco->vecino); } } // Tratamos el caso especial de que haya jugadores para los que t es inalcanzable for (int v = 0; v < vertices.size(); v++) if (! visitado[v]) { for (int i = jugadoresEnVertice[v]; i > 0; i--) jugadores[contador++] = v; if (contador == jugadores.size()) return; } }