Algoritmos y Estructuras de Datos (VJ1215)

Lo que nos piden es asignar un color diferente a cada componente fuertemente conexa de un grafo dirigido. Podemos utilizar el algoritmo de Kosaraju-Sharir para ello.

void GrafoDirigido::KosarajuSharirEtapa1DFS(int v,
                                            vector<bool> & visitado,
                                            stack<int> & ordenDeTerminacion) const {

   visitado[v] = true;
   for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente)
      if (! visitado[arco->vecino])
	 KosarajuSharirEtapa1DFS(arco->vecino, visitado, ordenDeTerminacion);
   ordenDeTerminacion.push(v);

}

void GrafoDirigido::KosarajuSharirEtapa2DFS(int v,
                                            vector<int> & color,
                                            int contadorColor) const {

   color[v] = contadorColor;
   for (Arco * arco = vertices[v].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente)
      if (color[arco->vecino] == -1)
	 KosarajuSharirEtapa2DFS(arco->vecino, color, contadorColor);

}

vector<int> GrafoDirigido::colorearConectados() const {

   int cantidadDeVertices = vertices.size();
   vector<bool> visitado(cantidadDeVertices, false);
   vector<int> color(cantidadDeVertices, -1);
   stack<int> ordenDeTerminacion;

   int contadorColor = 0, origen;

   for (origen = 0; origen < cantidadDeVertices; origen++)
      if (! visitado[origen])
	 KosarajuSharirEtapa1DFS(origen, visitado, ordenDeTerminacion);

   while (! ordenDeTerminacion.empty()) {
      origen = ordenDeTerminacion.top();
      ordenDeTerminacion.pop();
      if (color[origen] == -1)
	 KosarajuSharirEtapa2DFS(origen, color, ++contadorColor);
   }
   
   return color;

}