Saltar a contenido

UVa 10305, Ordering Tasks

Enunciado y envío: https://vjudge.net/problem/UVA-10305. La página pide cuenta para ver el enunciado.

Enunciado resumido

Hay \(n\) tareas (\(1 \le n \le 100\)), numeradas de 1 a \(n\), y \(m\) relaciones i j: la tarea i va antes que la j. Se imprime, en una línea, un orden en que se pueden hacer todas. La entrada trae varios casos y termina con 0 0. El juez acepta cualquier orden correcto.

La idea

Es el orden topológico con el algoritmo de Kahn. Se cuenta cuántas relaciones llegan a cada tarea, su grado de entrada, y se ponen en una cola las que no tienen ninguna. Al sacar una tarea se imprime y se baja en uno el grado de las que dependen de ella; la que llega a cero entra a la cola. El grado se cuenta mientras se leen los datos: con cada relación i j se suma 1 a entrada[j].

Con la muestra, la cola arranca con 1 y 4 y la salida es 1 4 2 5 3, la misma del enunciado.

Cómo leer la entrada en C++

int n, m;
scanf("%d %d", &n, &m);
while (n != 0 || m != 0) {
  vector<vector<int> > adj(n + 1);
  vector<int> entrada(n + 1, 0);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    adj[a].push_back(b);
    entrada[b] = entrada[b] + 1;
  }
  // aquí va Kahn
  scanf("%d %d", &n, &m);
}

Trampas

  • Las tareas se numeran desde 1: los vectores llevan \(n + 1\) posiciones.
  • Puede haber \(m = 0\) con \(n > 0\): todas las tareas entran a la cola al empezar.
  • Los números de una línea van separados por un espacio, sin espacio al final.

Complejidad

\(O(n + m)\) por caso: cada tarea entra y sale de la cola una vez y cada relación se mira una vez.