Este problema, a primera vista, parece sencillo. La idea principle se puede concebir rápidamente, y la implementación inicial podría tomar unos minutos. Sin embargo, es común encontrar errores (WA) debido a casos de borde o detalles no considerados, lo que requiere tiempo adicional para depurar el código. La complejidad del código no es excesiav.

Nota: Después de trabajar con estructuras de datos complejas como árboles de segmentos y descomposiciones de árboles en cadenas, resolver un problema más directo como este puede ser un buen descanso.

Este análisis busca ser lo más claro y accesible posible.

Descripción del Problema

Se proporciona un grafo dirigido. El objetivo es determinar la longitud máxima de un camino que se puede seguir partiendo desde cualquier ciudad, llegando a cualquier otra ciudad (incluida la ciudad de origen), sin exceder un número determinado de ciudades.

Análisis y Solución

Al recibir el problema, el primer paso es examinar los ejemplos proporcionados para compernder la dinámica.

• Ciudad 1: 1 (camino de longitud 1)
• Ciudad 2: 1 -> 2 (camino de longitud 2)
• Ciudad 3: 1 -> 2 -> 3 (camino de longitud 3)
• Ciudad 4: 1 -> 2 -> 3 -> 4 (camino de longitud 4)
• Ciudad 5: 1 -> 2 -> 5 (camino de longitud 3)

Realizando un análisis manual, se observa que la estrategia más efectiva consiste en iniciar la expansión desde los nodos con una in-degree (grado de entrada) de cero.

Esto sugiere que se puede implementar una solución utilizando búsqueda en anchura (BFS) o búsqueda en profundidad (DFS).

Se optó por BFS, implementada a través del algoritmo SPFA (Shortest Path Faster Algorithm), que es adecuado para este tipo de problemas en grafos dirigidos.

Implementación Inicial (con errores potenciales)

A continuación, se presenta una primera versión del código:

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

int main() {
    int num_ciudades, num_conexiones;
    std::cin >> num_ciudades >> num_conexiones;

    std::vector<std::vector<int>> grafo(num_ciudades + 1);
    std::vector<int> distancias(num_ciudades + 1, 0);
    std::vector<bool> en_cola(num_ciudades + 1, false);

    for (int k = 0; k < num_conexiones; ++k) {
        int origen, destino;
        std::cin >> origen >> destino;
        grafo[origen].push_back(destino);
    }

    std::queue<int> q;
    // Inicialización asumiendo que la ciudad 1 es el único punto de partida
    q.push(1);
    distancias[1] = 1;
    en_cola[1] = true;

    while (!q.empty()) {
        int actual = q.front();
        q.pop();
        en_cola[actual] = false;

        for (int vecino : grafo[actual]) {
            if (distancias[vecino] < distancias[actual] + 1) {
                distancias[vecino] = distancias[actual] + 1;
                if (!en_cola[vecino]) {
                    q.push(vecino);
                    en_cola[vecino] = true;
                }
            }
        }
    }

    for (int i = 1; i <= num_ciudades; ++i) {
        std::cout << distancias[i] << std::endl;
    }

    return 0;
}

Este código funciona correctamente con los ejemplos dados. Sin embargo, al enviarlo a la plataforma de evaluación, puede resultar en múltiples fallos (WA).

Tras revisar la solución o la descripción del problema, se descubre una omisión crucial: puede haber múltiples ciudades con una in-degree de cero, no solo la ciudad 1.

La premisa de que "se asume que se parte de la ciudad 1" podría ser incorrecta o incompleta. La pregunta busca la ruta más larga posible desde *cualquier* ciudad de inicio válida.

Solución Optimizada y Correcta

La versión corregida debe identificar e inicializar todos los nodos con in-degree cero como puntos de partida potenciales.

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

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_ciudades, num_conexiones;
    std::cin >> num_ciudades >> num_conexiones;

    std::vector<std::vector<int>> grafo(num_ciudades + 1);
    std::vector<int> longitudes_camino(num_ciudades + 1, 0);
    std::vector<bool> en_cola_procesamiento(num_ciudades + 1, false);
    std::vector<bool> tiene_entrada(num_ciudades + 1, false); // Para marcar nodos con in-degree > 0

    for (int k = 0; k < num_conexiones; ++k) {
        int origen, destino;
        std::cin >> origen >> destino;
        grafo[origen].push_back(destino);
        tiene_entrada[destino] = true; // Marca el nodo destino como teniendo una conexión de entrada
    }

    std::queue<int> q;
    // Añadir todos los nodos sin conexiones de entrada como puntos de partida
    for (int i = 1; i <= num_ciudades; ++i) {
        if (!tiene_entrada[i]) {
            q.push(i);
            longitudes_camino[i] = 1; // La longitud mínima es 1 (la ciudad misma)
            en_cola_procesamiento[i] = true;
        }
    }

    while (!q.empty()) {
        int ciudad_actual = q.front();
        q.pop();
        en_cola_procesamiento[ciudad_actual] = false;

        for (int ciudad_siguiente : grafo[ciudad_actual]) {
            // Si encontramos un camino más largo hacia ciudad_siguiente
            if (longitudes_camino[ciudad_siguiente] < longitudes_camino[ciudad_actual] + 1) {
                longitudes_camino[ciudad_siguiente] = longitudes_camino[ciudad_actual] + 1;
                // Si el vecino no está actualmente en la cola para ser procesado, lo añadimos
                if (!en_cola_procesamiento[ciudad_siguiente]) {
                    q.push(ciudad_siguiente);
                    en_cola_procesamiento[ciudad_siguiente] = true;
                }
            }
        }
    }

    // Imprimir los resultados para cada ciudad
    for (int i = 1; i <= num_ciudades; ++i) {
        std::cout << longitudes_camino[i] << "\n";
    }

    return 0;
}

Con esta modificación, el código ahora maneja correctamente los múltiples puntos de inicio potenciales y debería pasar todas las pruebas.