CP-UPV Bootcamp - Capítulo 8

Capítulo 8: Teoría y Algoritmos de Grafos

PROBLEMAS DEL CAPÍTULO

Para acceder a los problemas de este capítulo, accede con tu usuario y contraseña a cpupv.contest.codeforces.com. Si no tienes usuario y contraseña, inscríbete aquí.

Índice de contenidos

1. Fundamentos y Propiedades de los Grafos
2. Representación de Grafos en Memoria
3. Algoritmos de Exploración y Búsqueda
4. Algoritmos de Caminos Mínimos
5. Orden Topológico y Algoritmo de Kahn
6. Árboles de Recubrimiento Mínimo (MST)
7. Componentes Fuertemente Conexas (SCC)
8. Conceptos Especiales en Árboles
9. Problemas de práctica

1. Fundamentos y Propiedades de los Grafos

Con origen histórico en el famoso problema de los puentes de Königsberg formulado por Leonhard Euler, la Teoría de Grafos es la rama de la informática y las matemáticas que estudia las relaciones abstractas entre entidades discretas. Un grafo $G = (V, E)$ queda formalmente definido por dos conjuntos:

Vértices o Nodos ($V$): Representan los elementos individuales del sistema (por ejemplo, personas en una red social, servidores en una red o intersecciones en un mapa).
Aristas o Arcos ($E$): Representan las relaciones o conexiones entre pares de vértices (por ejemplo, amistades, cables de red o calles).

1.1. Grados de un Vértice

El grado de un vértice es la cantidad de aristas conectadas a él. En grafos dirigidos diferenciamos entre el grado entrante ($in\text{-}degree$), que mide cuántas aristas apuntan hacia el nodo, y el grado saliente ($out\text{-}degree$), que mide cuántas aristas salen de él.

Un teorema fundamental es el Lema del Apretón de Manos: la suma de los grados de todos los vértices es siempre igual al doble del número de aristas ($\sum \text{deg}(v) = 2|E|$). Esto implica que la suma de grados siempre es un número par.

1.2. Clasificación de Grafos

Dirigidos vs. No Dirigidos: En un grafo no dirigido las relaciones son simétricas ($u \leftrightarrow v$). En un grafo dirigido las aristas tienen una dirección estricta ($u \to v$).
Ponderados vs. No Ponderados: En los grafos ponderados, cada arista lleva asociado un peso numérico $w(u, v)$ que representa una distancia, costo, tiempo o capacidad.
Bipartitos: Grafos cuyos vértices se pueden dividir en dos conjuntos disjuntos de modo que no existan aristas entre vértices del mismo conjunto. Una propiedad clave es que no contienen ciclos de longitud impar.
DAG (Directed Acyclic Graph): Grafo dirigido que no contiene ningún ciclo. Son la base para modelar dependencias, tareas en secuencia y algoritmos de programación dinámica.
Árboles: Un caso especial de grafo no dirigido que es conexo y no tiene ciclos. Un árbol con $V$ vértices siempre tiene exactamente $E = V - 1$ aristas.

2. Representación de Grafos en Memoria

La forma en la que almacenamos un grafo en memoria determina de manera crítica el tiempo de ejecución y la cantidad de memoria que consumirá nuestra solución.

Estructura	Memoria	Verificar arista $(u, v)$	Explorar vecinos de $u$	Uso ideal
Matriz de Adyacencia	$\mathcal{O}(V^2)$	$\mathcal{O}(1)$	$\mathcal{O}(V)$	Grafos muy densos ($E \approx V^2$) o $V \le 2500$
Lista de Adyacencia	$\mathcal{O}(V + E)$	$\mathcal{O}(\text{grado}(u))$	$\mathcal{O}(\text{grado}(u))$	Grafos dispersos ($E \ll V^2$), el estándar universal en CP
Lista de Aristas	$\mathcal{O}(E)$	$\mathcal{O}(E)$	$\mathcal{O}(E)$	Algoritmos basados en aristas (Kruskal, Bellman-Ford)

2.1. Matriz de Adyacencia

Consiste en una tabla bidimensional de tamaño $V \times V$. La celda adj[u][v] contiene el peso de la arista $u \to v$ o $0$ si no están conectados. Es idónea para comprobar si existe conexión entre dos nodos en tiempo constante $\mathcal{O}(1)$, pero resulta ineficiente para iterar sobre los vecinos de un nodo específico porque obliga a revisar las $V$ columnas de su fila.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int V = 5; // Nodos del 0 al V-1
    // Inicializamos matriz V x V con 0 (sin conexión)
    vector<vector<int>> adj(V, vector<int>(V, 0));

    // Añadir arista no dirigida entre u=0 y v=1 con peso w=7
    int u = 0, v = 1, w = 7;
    adj[u][v] = w;
    adj[v][u] = w;

    // Verificar si existe arista entre u y v: O(1)
    if (adj[0][1] != 0) cout << "Existe arista con peso " << adj[0][1] << "\n";

    // Recorrer todos los vecinos de u: O(V)
    for (int i = 0; i < V; i++) {
        if (adj[u][i] != 0) {
            cout << "Vecino de " << u << ": " << i << " con peso " << adj[u][i] << "\n";
        }
    }
}

V = 5
# Inicializamos matriz V x V con 0
adj = [[0] * V for _ in range(V)]

# Añadir arista no dirigida entre 0 y 1 con peso 7
u, v, w = 0, 1, 7
adj[u][v] = w
adj[v][u] = w

# Verificar si existe arista: O(1)
if adj[0][1] != 0:
    print(f"Existe arista con peso {adj[0][1]}")

# Recorrer vecinos: O(V)
for i in range(V):
    if adj[u][i] != 0:
        print(f"Vecino de {u}: {i} con peso {adj[u][i]}")

public class Main {
    public static void main(String[] args) {
        int V = 5;
        int[][] adj = new int[V][V];

        int u = 0, v = 1, w = 7;
        adj[u][v] = w;
        adj[v][u] = w;

        if (adj[0][1] != 0) {
            System.out.println("Existe arista con peso " + adj[0][1]);
        }

        for (int i = 0; i < V; i++) {
            if (adj[u][i] != 0) {
                System.out.println("Vecino de " + u + ": " + i + " con peso " + adj[u][i]);
            }
        }
    }
}

2.2. Lista de Adyacencia

Es un vector de listas dinámicas donde la posición adj[u] contiene únicamente los nodos vecinos de $u$. Es la estructura predilecta en programación competitiva porque solo almacena la información de las aristas reales que existen, reduciendo el consumo de memoria a $\mathcal{O}(V + E)$ y permitiendo iterar por los vecinos en tiempo proporcional al grado del nodo.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int V = 5;
    // Lista de adyacencia guardando pares {destino, peso}
    vector<vector<pair<int, int>>> adj(V);

    // Añadir arista no dirigida entre u=0 y v=1 con peso w=7
    int u = 0, v = 1, w = 7;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});

    // Recorrer los vecinos de u: O(grado(u))
    for (auto& edge : adj[u]) {
        int vecino = edge.first;
        int peso = edge.second;
        cout << "Vecino de " << u << ": " << vecino << " con peso " << peso << "\n";
    }
}

V = 5
# Lista de adyacencia guardando tuplas (destino, peso)
adj = [[] for _ in range(V)]

u, v, w = 0, 1, 7
adj[u].append((v, w))
adj[v].append((u, w))

# Recorrer vecinos: O(grado(u))
for vecino, peso in adj[u]:
    print(f"Vecino de {u}: {vecino} con peso {peso}")

import java.util.*;

class Edge {
    int to, weight;
    Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

public class Main {
    public static void main(String[] args) {
        int V = 5;
        List<List<Edge>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());

        int u = 0, v = 1, w = 7;
        adj.get(u).add(new Edge(v, w));
        adj.get(v).add(new Edge(u, w));

        for (Edge edge : adj.get(u)) {
            System.out.println("Vecino de " + u + ": " + edge.to + " con peso " + edge.weight);
        }
    }
}

2.3. Lista de Aristas

Es un vector lineal donde cada elemento representa una tupla $(u, v, w)$. No organiza los vecinos por nodo, pero facilita la ordenación global de todas las conexiones por peso, requisito indispensable en algoritmos voraces como Kruskal o relajaciones masivas como Bellman-Ford.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Arista {
    int u, v, peso;
};

int main() {
    vector<Arista> aristas;

    // Añadir aristas
    aristas.push_back({0, 1, 7});
    aristas.push_back({1, 2, 3});
    aristas.push_back({0, 2, 11});

    // Ordenar aristas por peso (clave para Kruskal)
    sort(aristas.begin(), aristas.end(), [](const Arista& a, const Arista& b) {
        return a.peso < b.peso;
    });

    // Recorrer todas las aristas: O(E)
    for (const auto& e : aristas) {
        cout << e.u << " -> " << e.v << " (peso: " << e.peso << ")\n";
    }
}

# Lista de tuplas (peso, u, v) para ordenar directamente por peso
aristas = []

aristas.append((7, 0, 1))
aristas.append((3, 1, 2))
aristas.append((11, 0, 2))

# Ordenar por peso
aristas.sort()

# Recorrer todas las aristas: O(E)
for peso, u, v in aristas:
    print(f"{u} -> {v} (peso: {peso})")

import java.util.*;

class Arista implements Comparable<Arista> {
    int u, v, peso;
    Arista(int u, int v, int peso) {
        this.u = u;
        this.v = v;
        this.peso = peso;
    }
    @Override
    public int compareTo(Arista o) {
        return Integer.compare(this.peso, o.peso);
    }
}

public class Main {
    public static void main(String[] args) {
        List<Arista> aristas = new ArrayList<>();

        aristas.add(new Arista(0, 1, 7));
        aristas.add(new Arista(1, 2, 3));
        aristas.add(new Arista(0, 2, 11));

        Collections.sort(aristas);

        for (Arista e : aristas) {
            System.out.println(e.u + " -> " + e.v + " (peso: " + e.peso + ")");
        }
    }
}

3. Algoritmos de Exploración y Búsqueda

Los algoritmos de exploración recorren los vértices del grafo siguiendo reglas sistemáticas. Son la herramienta fundamental para comprobar conectividad, encontrar componentes conexas o calcular caminos mínimos en grafos no ponderados.

3.1. BFS (Breadth-First Search) y 0-1 BFS

El BFS (Búsqueda en Anchura) explora el grafo nivel por nivel desde un nodo inicial utilizando una cola (Queue). Al procesar primero todos los nodos situados a distancia $1$, luego los situados a distancia $2$, etc., garantiza hallar la distancia mínima (en número de aristas) en tiempo $\mathcal{O}(V + E)$.

void bfs(int start, const vector<vector<int>>& adj, vector<int>& dist) {
    int V = adj.size();
    dist.assign(V, -1);
    queue<int> q;

    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

from collections import deque

def bfs(start, V, adj):
    dist = [-1] * V
    q = deque([start])
    dist[start] = 0

    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

import java.util.*;

static void bfs(int start, List<List<Integer>> adj, int[] dist) {
    Arrays.fill(dist, -1);
    Queue<Integer> q = new LinkedList<>();

    dist[start] = 0;
    q.add(start);

    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.add(v);
            }
        }
    }
}

0-1 BFS: Cuando las aristas de un grafo tienen únicamente pesos $0$ o $1$, el algoritmo de Dijkstra resulta innecesariamente lento. Podemos usar una cola de doble extremo (std::deque): si atravesamos una arista de peso $0$, insertamos el nodo destino por el frente (para procesarlo de inmediato); si pesa $1$, lo insertamos por el fondo. Esto mantiene la cola ordenada de forma óptima en tiempo $\mathcal{O}(V + E)$.

void zeroOneBFS(int start, const vector<vector<pair<int, int>>>& adj, vector<int>& dist) {
    int V = adj.size();
    dist.assign(V, 1e9);
    deque<int> dq;

    dist[start] = 0;
    dq.push_back(start);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second; // w solo puede ser 0 o 1

            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }
}

from collections import deque

def zero_one_bfs(start, V, adj):
    dist = [float('inf')] * V
    dq = deque([start])
    dist[start] = 0

    while dq:
        u = dq.popleft()
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

import java.util.*;

static void zeroOneBFS(int start, List<List<int[]>> adj, int[] dist) {
    Arrays.fill(dist, Integer.MAX_VALUE / 2);
    ArrayDeque<Integer> dq = new ArrayDeque<>();

    dist[start] = 0;
    dq.add(start);

    while (!dq.isEmpty()) {
        int u = dq.pollFirst();

        for (int[] edge : adj.get(u)) {
            int v = edge[0];
            int w = edge[1];

            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.addFirst(v);
                else dq.addLast(v);
            }
        }
    }
}

3.2. DFS (Depth-First Search) y Detección de Ciclos

El DFS (Búsqueda en Profundidad) explora el grafo adentrándose lo máximo posible por cada rama antes de retroceder (backtracking), utilizando la pila de llamadas recursivas.

Detección de Ciclos mediante 3 Colores: En grafos dirigidos, para saber si existe un ciclo debemos detectar si una arista apunta a un nodo que aún está en proceso de exploración en la pila recursiva actual. Para ello usamos 3 estados o colores:

Estado 0 (Blanco / No visitado): El nodo no se ha explorado.
Estado 1 (Gris / Visitando): El nodo está actualmente en la pila recursiva. Si encontramos una arista hacia un nodo gris, hemos detectado un ciclo.
Estado 2 (Negro / Procesado): El nodo y toda su rama han sido completamente explorados.

bool dfsCiclo(int u, const vector<vector<int>>& adj, vector<int>& estado) {
    estado[u] = 1; // Visitando (Gris)

    for (int v : adj[u]) {
        if (estado[v] == 1) return true; // Encontrada back-edge (Ciclo)
        if (estado[v] == 0 && dfsCiclo(v, adj, estado)) return true;
    }

    estado[u] = 2; // Procesado (Negro)
    return false;
}

def dfs_ciclo(u, adj, estado):
    estado[u] = 1 # Visitando
    for v in adj[u]:
        if estado[v] == 1:
            return True
        if estado[v] == 0 and dfs_ciclo(v, adj, estado):
            return True
    estado[u] = 2 # Procesado
    return False

static boolean dfsCiclo(int u, List<List<Integer>> adj, int[] estado) {
    estado[u] = 1;
    for (int v : adj.get(u)) {
        if (estado[v] == 1) return true;
        if (estado[v] == 0 && dfsCiclo(v, adj, estado)) return true;
    }
    estado[u] = 2;
    return false;
}

4. Algoritmos de Caminos Mínimos

Los algoritmos de caminos mínimos calculan la ruta de menor costo entre nodos en grafos ponderados. La elección del algoritmo depende de la presencia de pesos negativos y de si necesitamos distancias desde un único origen o entre todos los pares.

4.1. Dijkstra

El Algoritmo de Dijkstra calcula el camino más corto desde un nodo origen a todos los demás. Funciona mediante un enfoque voraz (greedy) apoyado en una cola de prioridad (min-heap): extrae en cada paso el nodo no visitado con la menor distancia acumulada y relaja sus aristas salientes. Su complejidad es $\mathcal{O}((V + E) \log V)$. Importante: Dijkstra asume que añadir aristas nunca reduce la distancia acumulada, por lo que falla si existen aristas con peso negativo.

void dijkstra(int source, const vector<vector<pair<int, int>>>& adj, vector<int>& dist) {
    int V = adj.size();
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist.assign(V, numeric_limits<int>::max());
    dist[source] = 0;
    pq.push({0, source});

    while (!pq.empty()) {
        int d = pq.top().first; 
        int u = pq.top().second;
        pq.pop();

        if (d > dist[u]) continue;

        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v}); 
            }
        }
    }
}

import heapq

def dijkstra(source, V, adj):
    dist = [float('inf')] * V
    dist[source] = 0
    pq = [(0, source)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue

        for v, weight in adj[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))
    return dist

import java.util.*;

static void dijkstra(int source, List<List<int[]>> adj, int[] dist) {
    int V = adj.size();
    Arrays.fill(dist, Integer.MAX_VALUE);
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

    dist[source] = 0;
    pq.add(new int[]{0, source});

    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int d = top[0], u = top[1];

        if (d > dist[u]) continue;

        for (int[] edge : adj.get(u)) {
            int v = edge[0], weight = edge[1];
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.add(new int[]{dist[v], v});
            }
        }
    }
}

4.2. Bellman-Ford

El Algoritmo de Bellman-Ford resuelve la limitación de Dijkstra admitiendo aristas con peso negativo. Se basa en el principio de que un camino simple en un grafo de $V$ vértices contiene como máximo $V - 1$ aristas. Por tanto, si relajamos la totalidad de las aristas del grafo $V - 1$ veces, garantizamos haber encontrado la distancia mínima. Si realizamos una iteración extra (la $V$-ésima) y alguna distancia vuelve a reducirse, que existe un ciclo de peso negativo alcanzable. Su complejidad es $\mathcal{O}(V \cdot E)$.

struct Arista { int u, v; long long peso; };

// Devuelve false si se detecta un ciclo negativo alcanzable desde source
bool bellmanFord(int n, int source, const vector<Arista>& aristas, vector<long long>& dist) {
    const long long INF = numeric_limits<long long>::max() / 2;
    dist.assign(n, INF);
    dist[source] = 0;

    for (int i = 0; i < n - 1; i++) {
        for (const auto& e : aristas) {
            if (dist[e.u] < INF && dist[e.u] + e.peso < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.peso;
            }
        }
    }

    // Ronda extra para detectar ciclos negativos
    for (const auto& e : aristas) {
        if (dist[e.u] < INF && dist[e.u] + e.peso < dist[e.v]) return false;
    }
    return true;
}

def bellman_ford(n, source, aristas):
    INF = float('inf')
    dist = [INF] * n
    dist[source] = 0

    for _ in range(n - 1):
        for u, v, peso in aristas:
            if dist[u] != INF and dist[u] + peso < dist[v]:
                dist[v] = dist[u] + peso

    hay_ciclo_negativo = False
    for u, v, peso in aristas:
        if dist[u] != INF and dist[u] + peso < dist[v]:
            hay_ciclo_negativo = True
            break

    return dist, hay_ciclo_negativo

import java.util.Arrays;
import java.util.List;

public class BellmanFord {
    static class Arista {
        int u, v; long peso;
        Arista(int u, int v, long peso) { this.u = u; this.v = v; this.peso = peso; }
    }

    static boolean bellmanFord(int n, int source, List<Arista> aristas, long[] dist) {
        final long INF = Long.MAX_VALUE / 2;
        Arrays.fill(dist, INF);
        dist[source] = 0;

        for (int i = 0; i < n - 1; i++) {
            for (Arista e : aristas) {
                if (dist[e.u] < INF && dist[e.u] + e.peso < dist[e.v]) {
                    dist[e.v] = dist[e.u] + e.peso;
                }
            }
        }

        for (Arista e : aristas) {
            if (dist[e.u] < INF && dist[e.u] + e.peso < dist[e.v]) return false;
        }
        return true;
    }
}

4.3. Floyd-Warshall

El Algoritmo de Floyd-Warshall es una solución elegante basada en programación dinámica que calcula los caminos mínimos entre todos los pares de vértices en tiempo $\mathcal{O}(V^3)$. La idea clave consiste en probar sistemáticamente cada nodo $k$ como posible punto intermedio en el camino entre $i$ y $j$. Es la opción ideal cuando el grafo es denso o cuando el número de vértices es pequeño ($V \le 400$).

void floydWarshall(int n, vector<vector<long long>>& dist) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

def floyd_warshall(n, dist):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

static void floydWarshall(int n, long[][] dist) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

5. Orden Topológico y Algoritmo de Kahn

Un Orden Topológico de un grafo dirigido es un ordenamiento lineal de sus vértices de manera que, para toda arista $u \to v$, el vértice $u$ aparece estrictamente antes que $v$. Solo existe en Grafos Dirigidos Acíclicos (DAG).

El Algoritmo de Kahn calcula dicho orden identificando secuencialmente vértices cuyo grado entrante ($in\text{-}degree$) es 0, lo que significa que no dependen de ningún prerrequisito pendiente. Al extraerlos de la cola, "eliminamos" sus aristas salientes y reducimos el grado entrante de sus vecinos. Si procesamos los $V$ vértices, el orden es válido; si quedan vértices con $in\text{-}degree > 0$, el grafo contiene un ciclo. Su complejidad es $\mathcal{O}(V + E)$.

vector<int> topoSortKahn(int n, const vector<vector<int>>& adj) {
    vector<int> indegree(n, 0);
    for (int u = 0; u < n; u++) {
        for (int v : adj[u]) indegree[v]++;
    }

    queue<int> q;
    for (int v = 0; v < n; v++) {
        if (indegree[v] == 0) q.push(v);
    }

    vector<int> orden;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        orden.push_back(u);

        for (int v : adj[u]) {
            if (--indegree[v] == 0) q.push(v);
        }
    }

    if ((int)orden.size() != n) return {}; // Detecta ciclo
    return orden;
}

from collections import deque

def topo_sort_kahn(n, adj):
    indegree = [0] * n
    for u in range(n):
        for v in adj[u]:
            indegree[v] += 1

    q = deque(v for v in range(n) if indegree[v] == 0)
    orden = []

    while q:
        u = q.popleft()
        orden.append(u)
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)

    return orden if len(orden) == n else []

import java.util.*;

public static List<Integer> topoSortKahn(int n, List<List<Integer>> adj) {
    int[] indegree = new int[n];
    for (int u = 0; u < n; u++) {
        for (int v : adj.get(u)) indegree[v]++;
    }

    ArrayDeque<Integer> q = new ArrayDeque<>();
    for (int v = 0; v < n; v++) {
        if (indegree[v] == 0) q.add(v);
    }

    List<Integer> orden = new ArrayList<>();
    while (!q.isEmpty()) {
        int u = q.poll();
        orden.add(u);
        for (int v : adj.get(u)) {
            if (--indegree[v] == 0) q.add(v);
        }
    }

    if (orden.size() != n) return new ArrayList<>();
    return orden;
}

6. Árboles de Recubrimiento Mínimo (MST)

Dado un grafo no dirigido, conexo y ponderado, un Árbol de Recubrimiento Mínimo (Minimum Spanning Tree - MST) es un subconjunto de aristas que conecta la totalidad de los vértices formando un árbol sin ciclos, de modo que la suma de sus pesos sea la mínima posible.

El Algoritmo de Kruskal sigue una estrategia voraz sobre las aristas: las ordena todas de menor a mayor peso y las recorre una a una. Incorpora una arista al MST únicamente si sus extremos $u$ y $v$ no pertenecen aún a la misma componente conexa, lo cual comprueba en tiempo prácticamente constante utilizando la estructura de datos Disjoint Set Union (DSU). Su complejidad es $\mathcal{O}(E \log V)$.

struct DSU {
    vector<int> p;
    DSU(int n) { p.resize(n); iota(p.begin(), p.end(), 0); }
    int find(int i) { return p[i] == i ? i : p[i] = find(p[i]); }
    bool unite(int i, int j) {
        int root_i = find(i), root_j = find(j);
        if (root_i != root_j) { p[root_j] = root_i; return true; }
        return false;
    }
};

struct Edge { int u, v, w; };

long long kruskal(int V, vector<Edge>& edges) {
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) { return a.w < b.w; });
    DSU dsu(V);
    long long mst_cost = 0;
    int count = 0;

    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            mst_cost += e.w;
            if (++count == V - 1) break;
        }
    }
    return mst_cost;
}

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
    def find(self, i):
        if self.p[i] == i:
            return i
        self.p[i] = self.find(self.p[i])
        return self.p[i]
    def unite(self, i, j):
        root_i, root_j = self.find(i), self.find(j)
        if root_i != root_j:
            self.p[root_j] = root_i
            return True
        return False

def kruskal(V, edges):
    edges.sort(key=lambda x: x[2]) # Ordenar por peso
    dsu = DSU(V)
    mst_cost = 0
    count = 0

    for u, v, w in edges:
        if dsu.unite(u, v):
            mst_cost += w
            count += 1
            if count == V - 1:
                break
    return mst_cost

import java.util.*;

class DSU {
    int[] p;
    DSU(int n) {
        p = new int[n];
        for (int i = 0; i < n; i++) p[i] = i;
    }
    int find(int i) { return p[i] == i ? i : (p[i] = find(p[i])); }
    boolean unite(int i, int j) {
        int rootI = find(i), rootJ = find(j);
        if (rootI != rootJ) { p[rootJ] = rootI; return true; }
        return false;
    }
}

public class Kruskal {
    static class Edge implements Comparable<Edge> {
        int u, v, w;
        Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
        public int compareTo(Edge o) { return Integer.compare(this.w, o.w); }
    }

    static long kruskal(int V, List<Edge> edges) {
        Collections.sort(edges);
        DSU dsu = new DSU(V);
        long mstCost = 0;
        int count = 0;

        for (Edge e : edges) {
            if (dsu.unite(e.u, e.v)) {
                mstCost += e.w;
                if (++count == V - 1) break;
            }
        }
        return mstCost;
    }
}

7. Componentes Fuertemente Conexas (SCC)

En un grafo dirigido, una Componente Fuertemente Conexa (Strongly Connected Component - SCC) es un subconjunto maximal de vértices tal que, para cualquier par de nodos $u$ y $v$ dentro del subconjunto, existe un camino dirigido de $u$ a $v$ y también de $v$ a $u$. Si se "colapsa" cada SCC en un supernodo, el grafo resultante es siempre un DAG.

El Algoritmo de Kosajaru encuentra todas las SCC en tiempo $\mathcal{O}(V + E)$ mediante dos pasadas de DFS:

Ejecuta un DFS sobre el grafo original guardando los nodos en una pila según su tiempo de finalización (postorden).
Construye el grafo invertido (invirtiendo la dirección de todas las aristas).
Desapila los nodos uno a uno y ejecuta un segundo DFS sobre el grafo invertido; cada búsqueda identifica una SCC completa.

void dfs1(int u, const vector<vector<int>>& adj, vector<bool>& vis, vector<int>& order) {
    vis[u] = true;
    for (int v : adj[u]) if (!vis[v]) dfs1(v, adj, vis, order);
    order.push_back(u);
}

void dfs2(int u, const vector<vector<int>>& adj_inv, vector<bool>& vis, vector<int>& comp) {
    vis[u] = true;
    comp.push_back(u);
    for (int v : adj_inv[u]) if (!vis[v]) dfs2(v, adj_inv, vis, comp);
}

vector<vector<int>> kosaraju(int V, const vector<vector<int>>& adj) {
    vector<bool> vis(V, false);
    vector<int> order;

    for (int i = 0; i < V; i++) if (!vis[i]) dfs1(i, adj, vis, order);

    vector<vector<int>> adj_inv(V);
    for (int u = 0; u < V; u++) {
        for (int v : adj[u]) adj_inv[v].push_back(u);
    }

    fill(vis.begin(), vis.end(), false);
    vector<vector<int>> sccs;

    for (int i = V - 1; i >= 0; i--) {
        int u = order[i];
        if (!vis[u]) {
            vector<int> comp;
            dfs2(u, adj_inv, vis, comp);
            sccs.push_back(comp);
        }
    }
    return sccs;
}

def kosaraju(V, adj):
    vis = [False] * V
    order = []

    def dfs1(u):
        vis[u] = True
        for v in adj[u]:
            if not vis[v]:
                dfs1(v)
        order.append(u)

    for i in range(V):
        if not vis[i]:
            dfs1(i)

    adj_inv = [[] for _ in range(V)]
    for u in range(V):
        for v in adj[u]:
            adj_inv[v].append(u)

    vis = [False] * V
    sccs = []

    def dfs2(u, comp):
        vis[u] = True
        comp.append(u)
        for v in adj_inv[u]:
            if not vis[v]:
                dfs2(v, comp)

    for u in reversed(order):
        if not vis[u]:
            comp = []
            dfs2(u, comp)
            sccs.append(comp)

    return sccs

import java.util.*;

public class Kosaraju {
    static void dfs1(int u, List<List<Integer>> adj, boolean[] vis, List<Integer> order) {
        vis[u] = true;
        for (int v : adj.get(u)) if (!vis[v]) dfs1(v, adj, vis, order);
        order.add(u);
    }

    static void dfs2(int u, List<List<Integer>> adjInv, boolean[] vis, List<Integer> comp) {
        vis[u] = true;
        comp.add(u);
        for (int v : adjInv.get(u)) if (!vis[v]) dfs2(v, adjInv, vis, comp);
    }

    static List<List<Integer>> kosaraju(int V, List<List<Integer>> adj) {
        boolean[] vis = new boolean[V];
        List<Integer> order = new ArrayList<>();

        for (int i = 0; i < V; i++) if (!vis[i]) dfs1(i, adj, vis, order);

        List<List<Integer>> adjInv = new ArrayList<>();
        for (int i = 0; i < V; i++) adjInv.add(new ArrayList<>());
        for (int u = 0; u < V; u++) {
            for (int v : adj.get(u)) adjInv.get(v).add(u);
        }

        Arrays.fill(vis, false);
        List<List<Integer>> sccs = new ArrayList<>();

        for (int i = V - 1; i >= 0; i--) {
            int u = order.get(i);
            if (!vis[u]) {
                List<Integer> comp = new ArrayList<>();
                dfs2(u, adjInv, vis, comp);
                sccs.add(comp);
            }
        }
        return sccs;
    }
}

8. Conceptos Especiales en Árboles

Los árboles tienen estructuras y propiedades que permiten algoritmos sumamente optimizados:

Diámetro de un Árbol: Es la longitud del camino más largo entre dos nodos cualquiera. Se puede calcular en tiempo $\mathcal{O}(V)$ ejecutando dos BFS/DFS: el primero desde un nodo arbitrario para hallar el nodo más lejano $A$, y el segundo desde $A$ para hallar el nodo más lejano $B$. La distancia entre $A$ y $B$ es el diámetro.
Lowest Common Ancestor (LCA): El ancestro común más bajo entre dos nodos $u$ y $v$ en un árbol enraizado. Utilizando Binary Lifting (elevación binaria), precalculamos la tabla up[u][i] (el $2^i$-ésimo ancestro de $u$) en $\mathcal{O}(V \log V)$, lo que nos permite responder a consultas de LCA en tiempo $\mathcal{O}(\log V)$.

const int LOGN = 20;
vector<int> depth;
vector<vector<int>> up;

void dfsLCA(int u, int p, int d, const vector<vector<int>>& adj) {
    depth[u] = d;
    up[u][0] = p;
    for (int i = 1; i < LOGN; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for (int v : adj[u]) {
        if (v != p) dfsLCA(v, u, d + 1, adj);
    }
}

int getLCA(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = LOGN - 1; i >= 0; i--) {
        if (depth[u] - (1 << i) >= depth[v]) u = up[u][i];
    }
    if (u == v) return u;
    for (int i = LOGN - 1; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

LOGN = 20

def preprocess_lca(root, V, adj):
    depth = [0] * V
    up = [[0] * LOGN for _ in range(V)]

    def dfs(u, p, d):
        depth[u] = d
        up[u][0] = p
        for i in range(1, LOGN):
            up[u][i] = up[up[u][i - 1]][i - 1]
        for v in adj[u]:
            if v != p:
                dfs(v, u, d + 1)

    dfs(root, root, 0)

    def get_lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        for i in range(LOGN - 1, -1, -1):
            if depth[u] - (1 << i) >= depth[v]:
                u = up[u][i]
        if u == v:
            return u
        for i in range(LOGN - 1, -1, -1):
            if up[u][i] != up[v][i]:
                u = up[u][i]
                v = up[v][i]
        return up[u][0]

    return get_lca

import java.util.*;

public class LCA {
    static final int LOGN = 20;
    static int[] depth;
    static int[][] up;

    static void dfsLCA(int u, int p, int d, List<List<Integer>> adj) {
        depth[u] = d;
        up[u][0] = p;
        for (int i = 1; i < LOGN; i++) {
            up[u][i] = up[up[u][i - 1]][i - 1];
        }
        for (int v : adj.get(u)) {
            if (v != p) dfsLCA(v, u, d + 1, adj);
        }
    }

    static int getLCA(int u, int v) {
        if (depth[u] < depth[v]) { int tmp = u; u = v; v = tmp; }
        for (int i = LOGN - 1; i >= 0; i--) {
            if (depth[u] - (1 << i) >= depth[v]) u = up[u][i];
        }
        if (u == v) return u;
        for (int i = LOGN - 1; i >= 0; i--) {
            if (up[u][i] != up[v][i]) {
                u = up[u][i];
                v = up[v][i];
            }
        }
        return up[u][0];
    }
}

9. Problemas de práctica

Aplica los algoritmos de grafos resolviendo los problemas asignados en el concurso activo de nuestro bootcamp en Codeforces.