Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2403

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2403

Escalonamento Ótimo

 

Por OBI - Olimpíada Brasileira de Informática 2011 BR Brazil

Timelimit: 1

O SBC (System for Batch Computing) é um sistema operacional voltado para a execução sequencial de tarefas. O operador do sistema cria tarefas e o sistema operacional é responsável por agendar a execução destas tarefas.

Cada tarefa pode depender da conclusão de algumas tarefas para poder começar. Se uma tarefa A depende de uma tarefa B, a tarefa B deve terminar antes que a tarefa A inicie sua execução.

Além disto, cada tarefa possui uma prioridade. É sempre mais vantajoso para o sistema começar executando uma tarefa de mais alta prioridade, depois continuar executando uma tarefa de mais alta prioridade dentre as que sobraram e assim por diante.

Neste problema, será dado um inteiro N, que irá representar o número de tarefas no sistema. As tarefas serão numeradas de 0 até N−1. Tarefas com índice menor possuem prioridade maior, de forma que a tarefa 0 é a tarefa de mais alta prioridade, a tarefa 1 é a tarefa com a segunda maior prioridade e assim por diante, até a tarefa N−1, que é a tarefa com a menor prioridade. Além disso, serão dadas M relações de dependência entre as tarefas.

Seu objetivo será decidir se é possível executar as tarefas em alguma ordem. Caso seja possível, você deverá produzir uma ordem de execução ótima para as tarefas, isto é, desempate as ordens possíveis pela prioridade da primeira tarefa. Se o empate ainda persistir, desempate pela prioridade da segunda tarefa, e assim por diante.

 

Entrada

 

A primeira linha da entrada contém inteiros N (0 ≤ N ≤ 50000) e M (0 ≤ M ≤ 200000). As próximas M linhas descrevem, cada uma, uma dependência entre as tarefas da entrada. Cada uma dessas linhas irá conter dois inteiros A e B (0 ≤ AB < N) que indicam que a tarefa B depende da tarefa A, isto é, que a tarefa A deve terminar antes que a tarefa B inicie.

 

Saída

 

Se não for possível ordenar as tarefas de forma que as dependências sejam satisfeitas, imprima uma única linha contendo o caracter "*". Caso contrário, imprima N linhas contendo cada uma um número inteiro. O inteiro na i-ésima linha deve ser o índice da i-ésima tarefa a ser executada na ordem ótima de execução das tarefas.

 

 

 

Exemplos de Entrada Exemplos de Saída

3 1

2 0

1

2

0

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
#define MAXN 100100
int n, m, grau[MAXN];
vector<int> lista, grafo[MAXN];
priority_queue < int, vector<int>, greater < int> > fila;
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i  < = m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        grau[y]++;
        grafo[x].push_back(y);
    }
    for (int i = 0; i  <  n; i++)
        if (!grau[i]) fila.push(i);
    while (!fila.empty()) {
        int atual = fila.top();
        fila.pop();
        lista.push_back(atual);
        for (int i = 0; i  <  grafo[atual].size(); i++) {
            int v = grafo[atual][i];
            grau[v]--;
            if (!grau[v]) fila.push(v);
        }
    }
    if (lista.size()  <  n)
        printf("*\n");
    else
        for (int i = 0; i  <  lista.size(); i++) printf("%d\n", lista[i]);
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3 1
2 0

Output

x
+
cmd
1
2
0
Advertisements

Demonstration


Previous
#2402 Beecrowd Online Judge Solution 2402 Selos Solution in C, C++, Java, Js and Python
Next
#2405 Beecrowd Online Judge Solution 2405 Colorindo Solution in C, C++, Java, Js and Python