=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
Examen final - 2023/2024
23 de enero de 2024
Ejercicio 8
Borrador
=================================================================

Solucion
========

Basta con elegir un guerrero cualquiera (por ejemplo, el de la posicion 0) y comprobar si (i) todos
los demas guerreros son alcanzables desde el y (ii) el es alcanzable desde todos los demas.

Cada una de esas dos comprobaciones se puede hacer mediante una busqueda en profundidad desde el
vertice del guerrero elegido: la primera, empleando arcos de salida; la segunda, empleando arcos de
entrada.

Para no seguir recorriendo el grafo innecesariamente cuando ya se puede determinar el resultado, en
cada una de las dos busquedas podemos terminar cuando hemos visitado todos los guerreros, aunque no
hayamos visitado todos los vertices.

Coste temporal en el peor caso: O(|V| + |E| + n)


bool GrafoDirigido::todosFuertementeConectados(const vector<int> & posiciones) const {

   vector<int> guerrerosEnVertice(vertices.size(), 0);
   vector<bool> visitado(vertices.size(), false);
   
   for (int v : posiciones)
      guerrerosEnVertice[v]++;

   int contadorGuerreros = posiciones.size();
   if (! todosAlcanzablesDesdeGuerreroDFS(posiciones[0], visitado, contadorGuerreros, guerrerosEnVertice))
      return false;

   for (int i = 0; i < visitado.size(); i++)
      visitado[i] = false;
   contadorGuerreros = posiciones.size();
   return guerreroAlcanzablePorTodosDFS(posiciones[0], visitado, contadorGuerreros, guerrerosEnVertice);

}

bool GrafoDirigido::todosAlcanzablesDesdeGuerreroDFS(int v,
                                                     vector<bool> & visitado,
						     int & contadorGuerreros,
						     const vector<int> & guerrerosEnVertice) const {
   contadorGuerreros -= guerrerosEnVertice[v];
   if (contadorGuerreros == 0)
      return true;
   visitado[v] = true;
   for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente)
      if (! visitado[arco->vecino])
	 if (todosAlcanzablesDesdeGuerreroDFS(arco->vecino, visitado, contadorGuerreros, guerrerosEnVertice))
	    return true;
   return false;
}

bool GrafoDirigido::guerreroAlcanzablePorTodosDFS(int v,
                                                  vector<bool> & visitado,
						  int & contadorGuerreros,
						  const vector<int> & guerrerosEnVertice) const {
   contadorGuerreros -= guerrerosEnVertice[v];
   if (contadorGuerreros == 0)
      return true;
   visitado[v] = true;
   for (Arco * arco = vertices[v].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente)
      if (! visitado[arco->vecino])
	 if (guerreroAlcanzablePorTodosDFS(arco->vecino, visitado, contadorGuerreros, guerrerosEnVertice))
	    return true;
   return false;
}