Algoritmos y Estructuras de Datos (VJ1215)

bool GrafoDirigido::esFuertementeConexo() const {

   return todosAlcanzablesDesdeVertice(0) && verticeAlcanzableDesdeTodos(0);

}


bool GrafoDirigido::todosAlcanzablesDesdeVertice(int origen) const {

   vector<bool> visitado(vertices.size(), false);
   queue<int> cola;
   int contadorVisitados;

   visitado[origen] = true;
   contadorVisitados = 1;
   cola.push(origen);

   while (! cola.empty()) {
      int v = cola.front();
      cola.pop();
      for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente)
	 if (! visitado[arco->vecino]) {
	    visitado[arco->vecino] = true;
	    contadorVisitados++;
	    cola.push(arco->vecino);
	 }
   }

   // cout << "Cantidad de vertices alcanzables desde " << origen << ": " << contadorVisitados << endl;

   return contadorVisitados == vertices.size();

}


bool GrafoDirigido::verticeAlcanzableDesdeTodos(int destino) const {

   vector<bool> visitado(vertices.size(), false);
   queue<int> cola;
   int contadorVisitados;

   visitado[destino] = true;
   contadorVisitados = 1;
   cola.push(destino);

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

   //  cout << "Cantidad de vertices desde los que se puede alcanzar " << destino << ": " << contadorVisitados << endl;

   return contadorVisitados == vertices.size();

}