Fundamentos del Ordenamienot Topológico

El ordenamiento topológico es una secuencia lineal de los vértices de un grafo dirigido acíclico (DAG), tal que para cada arista dirigida u -> v, el vértice u aparece antes que v en la ordenación. Si el grafo contiene ciclos, no es posible obtener un ordenamiento topológico.

Implementación Estándar de Ordenamiento Topológico

Utilizamos el algoritmo de Kahn, el cual se basa en el manejo de los grados de entrada (in-degree) de los nodos. Los nodos con grado de entrada cero se procesan primero y se añaden a una cola.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 100005;
vector<int> adj[MAXN];
int grado_entrada[MAXN];
int orden[MAXN];
int n;

void ejecutar_topo() {
    queue<int> cola;
    for (int i = 1; i <= n; i++) {
        if (grado_entrada[i] == 0) cola.push(i);
    }

    int total = 0;
    while (!cola.empty()) {
        int actual = cola.front();
        cola.pop();
        orden[total++] = actual;

        for (int vecino : adj[actual]) {
            if (--grado_entrada[vecino] == 0) {
                cola.push(vecino);
            }
        }
    }

    for (int i = 0; i < total; i++) {
        cout << orden[i] << (i == total - 1 ? "" : " ");
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int destino;
        while (cin >> destino && destino != 0) {
            adj[i].push_back(destino);
            grado_entrada[destino]++;
        }
    }
    ejecutar_topo();
    return 0;
}

Determinación de Consistencia y Unicidad

En problemas donde se dan relaciones de orden (ej. A < B), el ordenamiento topológico permite detectar tres estados: si se ha formado una secuencia única, si existe una inconsistencia (ciclo) o si los datos son insuficientes para determinar el orden completo.

// Fragmento de lógica para determinar el estado de la secuencia
bool verificar_topo(int n_nodos, vector<int>* lista_adj, int* deg_in, vector<int>& res) {
    queue<int> q;
    int temp_deg[30];
    for(int i=0; i<n_nodos; i++) {
        temp_deg[i] = deg_in[i];
        if(temp_deg[i] == 0) q.push(i);
    }

    bool unico = true;
    res.clear();
    while(!q.empty()) {
        if(q.size() > 1) unico = false;
        int u = q.front(); q.pop();
        res.push_back(u);
        for(int v : lista_adj[u]) {
            if(--temp_deg[v] == 0) q.push(v);
        }
    }
    if(res.size() < n_nodos) return false; // Ciclo detectado
    return true; 
}

Orientación de Aristas en Grafos Mixtos

Si se tiene un grafo con aristas dirigidas que ya forman un DAG y se desea orientar aristas no dirigidas sin crear ciclos, la estrategia consiste en calcular el orden topológico basado en las aristas dirigidas existentes. Para cualquier arista no dirigida (u, v), se orienta de u a v si el índice topológico de u es menor que el de v.

Cierre Transitivo con Floyd-Warshall

Para determinar la relación entre todos los pares de nodos (conectividad completa), el algoritmo de Floyd-Warshall es eficaz en grafos pequeños. Si f[i][j] es verdadero, significa que existe un camino de i a j.

void calcular_clausura(int n, int mat[105][105]) {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                mat[i][j] |= (mat[i][k] & mat[k][j]);
}

Ordenamiento Topológico con Prioridad Especial

A veces se requiere que los elementos con menor valor nominal aparezcan lo más tarde posible en ciertas restricciones. Esto se resuelve construyendo el grafo de manera inversa y utilizando una cola de prioridad (max-heap) para obtener el orden lexicográfico máximo del grafo reverso, lo que resulta en el orden "mínimo" deseado al invertir el resultado final.

void resolver_prioridad() {
    priority_queue<int> pq;
    // Se insertan nodos con grado de entrada 0 en el grafo invertido
    for(int i = 1; i <= n; i++) if(grado[i] == 0) pq.push(i);
    
    vector<int> resultado;
    while(!pq.empty()){
        int u = pq.top(); pq.pop();
        resultado.push_back(u);
        for(int v : adj_rev[u]){
            if(--grado[v] == 0) pq.push(v);
        }
    }
    // El orden final es la inversión de 'resultado'
}

Componentes Fuertemente Conectados (SCC) y Condensación

El algoritmo de Tarjan permite identificar SCC en grafos dirigidos. Al colapsar cada SCC en un único "supernodo", el grafo resultante es un DAG. Esto es crucial para resolver problemas de caminos máximos o accesibilidad.

void tarjan(int u) {
    dfn[u] = low[u] = ++tiempo;
    pila.push(u);
    en_pila[u] = true;

    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (en_pila[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (low[u] == dfn[u]) {
        int v;
        id_scc++;
        do {
            v = pila.top();
            pila.pop();
            en_pila[v] = false;
            pertenencia[v] = id_scc;
            tamano_scc[id_scc]++;
        } while (u != v);
    }
}

Accesibilidad en DAGs Condensados

Después de realizar la condensación de un grafo, el número de nodos adicionales necesarios para hacer que todos los nodos sean alcanzables desde un origen específico suele estar relacionado con el número de nodos que tienen un grado de entrada de cero en el DAG condensado. Si el nodo origen pertenece a un SCC con grado de entrada cero, este no cuenta como una arista adicional necesaria.

int calcular_aristas_necesarias(int origen_scc, int total_sccs, int* in_degree_scc) {
    int contador = 0;
    for (int i = 1; i <= total_sccs; i++) {
        if (in_degree_scc[i] == 0) {
            contador++;
        }
    }
    // Si el origen ya tiene grado de entrada 0 en el DAG, restamos 1 porque ya empezamos ahí
    return contador - (in_degree_scc[origen_scc] == 0 ? 1 : 0);
}

Conectividad y Puentes en Grafos No Dirigidos

Aunque el enfoque principle es en grafos dirigidos, la detección de puentes mediante DFS es fundamental para asegurar que un grafo no dirigido pueda convertirse en un grafo fuertemente conectado mediante la orientación de sus aristas. Si no existen puentes, siempre es posible orientar las aristas para formar un SCC único.