Orientación fuerte
Una orientación fuerte de un grafo no dirigido es una asignación de una dirección a cada arista que lo convierte en un grafo fuertemente conexo. Es decir, después de la orientación deberíamos poder visitar cualquier vértice desde cualquier vértice siguiendo las aristas dirigidas.
Solución
Por supuesto, esto no se puede hacer en todo grafo. Consideremos un puente en un grafo. Tenemos que asignarle una dirección y al hacerlo hacemos que este puente sea “cruzable” en una sola dirección. Eso significa que no podemos ir de uno de los extremos del puente al otro, así que no podemos hacer el grafo fuertemente conexo.
Ahora consideremos un DFS a través de un grafo conexo sin puentes. Claramente, visitaremos cada vértice. Y como no hay puentes, podemos quitar cualquier arista del árbol DFS y todavía ser capaces de ir de debajo de la arista a encima de la arista usando un camino que contiene al menos una arista de retroceso. De esto se sigue que desde cualquier vértice podemos ir a la raíz del árbol DFS. También, desde la raíz del árbol DFS podemos visitar cualquier vértice que elijamos. ¡Encontramos una orientación fuerte!
En otras palabras, para orientar de forma fuerte un grafo conexo sin puentes, ejecutamos un DFS sobre él y hacemos que las aristas del árbol DFS apunten alejándose de la raíz del DFS y todas las demás aristas del descendiente al ancestro en el árbol DFS.
El resultado de que los grafos conexos sin puentes son exactamente los grafos que tienen orientaciones fuertes se llama teorema de Robbins.
Extensión del problema
Consideremos el problema de encontrar una orientación del grafo de modo que el número de SCC sea mínimo.
Por supuesto, cada componente del grafo se puede considerar por separado. Ahora, como solo los grafos sin puentes son fuertemente orientables, quitemos temporalmente todos los puentes. Terminamos con cierto número de componentes sin puentes (exactamente cuántas componentes había al principio + cuántos puentes había) y sabemos que podemos orientar de forma fuerte cada una de ellas.
Solo se nos permitía orientar aristas, no quitarlas, pero resulta que podemos orientar los puentes de forma arbitraria. Por supuesto, la forma más fácil de orientarlos es ejecutar el algoritmo descrito arriba sin modificaciones sobre cada componente conexa original.
Implementación
Aquí, la entrada es n — el número de vértices, m — el número de aristas, luego m líneas que describen las aristas.
La salida es el número mínimo de SCC en la primera línea y en la segunda línea
una cadena de m caracteres,
ya sea > — que nos dice que la arista correspondiente de la entrada
está orientada del vértice izquierdo al derecho (como en la entrada),
o < — lo contrario.
Este es un algoritmo de búsqueda de puentes modificado para orientar también las aristas; también se pueden orientar las aristas como un primer paso y contar las SCC en el grafo orientado como un segundo.
vector<vector<pair<int, int>>> adj; // lista de adyacencia - pares vértice y arista
vector<pair<int, int>> edges;
vector<int> tin, low;
int bridge_cnt;
string orient;
vector<bool> edge_used;
void find_bridges(int v) {
static int time = 0;
low[v] = tin[v] = time++;
for (auto p : adj[v]) {
if (edge_used[p.second]) continue;
edge_used[p.second] = true;
orient[p.second] = v == edges[p.second].first ? '>' : '<';
int nv = p.first;
if (tin[nv] == -1) { // si nv aún no fue visitado
find_bridges(nv);
low[v] = min(low[v], low[nv]);
if (low[nv] > tin[v]) {
// un puente entre v y nv
bridge_cnt++;
}
} else {
low[v] = min(low[v], tin[nv]);
}
}
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
adj.resize(n);
tin.resize(n, -1);
low.resize(n, -1);
orient.resize(m);
edges.resize(m);
edge_used.resize(m);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d %d", &a, &b);
a--; b--;
adj[a].push_back({b, i});
adj[b].push_back({a, i});
edges[i] = {a, b};
}
int comp_cnt = 0;
for (int v = 0; v < n; v++) {
if (tin[v] == -1) {
comp_cnt++;
find_bridges(v);
}
}
printf("%d\n%s\n", comp_cnt + bridge_cnt, orient.c_str());
}