=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
Evaluacion continua - 2024/2025
13 de diciembre de 2024 (grafos)
Ejercicio
Borrador
=================================================================


Solucion apartado a
===================

Coste temporal en el peor caso: O(n + |V| + |E|)
Coste espacial en el peor caso sin contar el grafo: O(n + |V|)

bool GrafoDirigido::aSalvo(int jugador,
			   int vidas,
			   const vector<int> & guerreros) const {

   if (guerreros.size() < vidas)
      return true;
   
   vector<bool> visitado(vertices.size(), false);
   vector<int> guerrerosEnVertice(vertices.size(), 0);

   for (int v : guerreros)
      guerrerosEnVertice[v]++;

   vidas -= guerrerosEnVertice[jugador];
   if (vidas <= 0)
      return false;
   
   queue<int> cola;
 
   cola.push(jugador);
   visitado[jugador] = true;

   while (! cola.empty()) {
      int v = cola.front();
      cola.pop();
      for (Arco * arco = vertices[v].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente)
	 if (! visitado[arco->vecino]) {
	    vidas -= guerrerosEnVertice[arco->vecino];
	    if (vidas <= 0)
	       return false;
	    cola.push(arco->vecino);
	    visitado[arco->vecino] = true;
	 }
   }

   return true;

}


Solucion apartado b
===================

Coste temporal en el peor caso: O(n + |V| + |E|)
Coste espacial en el peor caso sin contar el grafo: O(n + |V|)

bool GrafoDirigido::aSalvoDFS(int v,
			      int & vidas,
			      const vector<int> & guerrerosEnVertice,
			      vector<bool> & visitado) const {
   
   vidas -= guerrerosEnVertice[v];
   if (vidas <= 0)
      return false;

   visitado[v] = true;

   for (Arco * arco = vertices[v].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente)
      if (! visitado[arco->vecino])
	 if (! aSalvoDFS(arco->vecino, vidas, guerrerosEnVertice, visitado))
	     return false;
	     
   return true;

}

bool GrafoDirigido::aSalvo(int jugador,
			   int vidas,
			   const vector<int> & guerreros) const {

   if (guerreros.size() < vidas)
      return true;
   
   vector<bool> visitado(vertices.size(), false);
   vector<int> guerrerosEnVertice(vertices.size(), 0);

   for (int v : guerreros)
      guerrerosEnVertice[v]++;

   return aSalvoDFS(jugador, vidas, guerrerosEnVertice, visitado);

}