Curso 2023/2024
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; }