Solução por Lucca Siaudzionis
Estes problemas que envolvem executar certas tarefas numa determinada ordem de prioridade geralmente estão relacionados a Ordenação Topológica. Há vários algoritmos para resolver um problemas de Ordenação Topológica (este artigo da Wikipédia explica bem o assunto). O problema Escalonamento Ótimo é mais difícil que uma simples ordenação topológica porque ele requer que as tarefas sejam, também, executadas por ordem crescente.
Pois bem, quando estamos resolvendo uma Ordenação Topológica, sempre temos uma "sacola" que contém todas as tarefas que já podem ser executadas a partir de agora (i.e. não precisam de nenhuma tarefa anterior ou as tarefas que necessita já foram executadas). Para imprimirmos sempre os número desta sacola em ordem crescente, podemos usar uma estrutura chama Fila de Prioridade (também conhecida como Heap). Heap (artigo da Wikipédia) é uma árvore binária em que o pai é sempre maior (no caso de uma max heap) ou menor que os filhos (no caso de uma min heap). Com isso, sabemos que, a qualquer instante, a raiz da árvore é o maior número na max heap (ou o menor, no caso da min heap).
Na biblioteca <queue> de C++ já há implementada a priority_queue, para que se possa usar a Heap sem você ter que montar ela inteira. Porém, recomendo que cada pessoa saiba montar uma heap. Vou disponibilizar o código nos dois casos.
Usando a estrutura montada:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <queue> | |
| #include <cstdio> | |
| #include <vector> | |
| #include <cstring> | |
| #include <algorithm> | |
| #define MAXN 50010 | |
| using namespace std; | |
| int nodes,edges; | |
| int grau[MAXN]; | |
| int marc[MAXN]; | |
| bool ciclo; | |
| vector<int> myv[MAXN]; | |
| vector<int> resp; | |
| priority_queue<int, vector<int>, greater<int> > heap; | |
| void dfs(int x){ | |
| marc[x] = 1; | |
| int l = myv[x].size(); | |
| for(int i = 0;i<l;i++){ | |
| if( marc[myv[x][i]] ) ciclo = 1; | |
| else dfs(myv[x][i]); | |
| } | |
| } | |
| int main(){ | |
| scanf("%d %d",&nodes,&edges); | |
| memset(grau,0,sizeof grau); | |
| for(int i = 1;i<=edges;i++){ | |
| int a,b; | |
| scanf("%d %d",&a,&b); | |
| a++; | |
| b++; | |
| grau[b]++; | |
| myv[a].push_back(b); | |
| } | |
| for(int i = 1;i<=nodes;i++) if(!grau[i]) heap.push(i); | |
| int cont = 0; | |
| while( !heap.empty() ){ | |
| cont++; | |
| int l = myv[heap.top()].size(); | |
| int cara = heap.top(); | |
| heap.pop(); | |
| for(int i = 0; i < l; i++ ){ | |
| grau[ myv[cara][i] ]--; | |
| if(!grau[myv[cara][i]]) heap.push(myv[cara][i]); | |
| } | |
| resp.push_back(cara); | |
| } | |
| if(cont < nodes) printf("*\n"); | |
| else for(int i = 0;i<nodes;i++) printf("%d\n",resp[i]-1); | |
| return 0; | |
| } |
Montando a própria estrutura:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <vector> | |
| #include <cstring> | |
| #include <algorithm> | |
| #define MAXN 50010 | |
| using namespace std; | |
| int nodes; | |
| int edges; | |
| int size; | |
| int grau[MAXN]; | |
| int heap[MAXN]; | |
| bool ciclo; | |
| bool marc[MAXN]; | |
| vector<int> resp; | |
| vector<int> myv[MAXN]; | |
| int left(int i){ | |
| return 2*i; | |
| } | |
| int right(int i){ | |
| return 2*i+1; | |
| } | |
| int parent(int i){ | |
| return i/2; | |
| } | |
| void heapify_down(int v){ | |
| int l = left(v); | |
| int r = right(v); | |
| int maior; | |
| if( l <= size && heap[l] < heap[v]) maior = l; | |
| else maior = v; | |
| if( r <= size && heap[r] < heap[maior]) maior = r; | |
| if( maior != v ){ | |
| int aux; | |
| aux = heap[maior]; | |
| heap[maior] = heap[v]; | |
| heap[v] = aux; | |
| heapify_down(maior); | |
| } | |
| } | |
| void heapify_up(int v){ | |
| if(v > 1){ | |
| int pai = parent(v); | |
| if(heap[v] < heap[pai]){ | |
| int aux = heap[v]; | |
| heap[v] = heap[pai]; | |
| heap[pai] = aux; | |
| heapify_up(pai); | |
| } | |
| } | |
| } | |
| void faz_tudo(){ | |
| //printf("%d\n",heap[1]-1); | |
| resp.push_back(heap[1]-1); | |
| int cara = heap[1]; | |
| int aux; | |
| aux = heap[1]; | |
| heap[1] = heap[size]; | |
| heap[size] = aux; | |
| size--; | |
| heapify_down(1); | |
| for(int i = 0;i<myv[cara].size();i++){ | |
| grau[myv[cara][i]]--; | |
| if(!grau[myv[cara][i]]){ | |
| heap[++size] = myv[cara][i]; | |
| heapify_up(size); | |
| } | |
| } | |
| if(size >= 1) faz_tudo(); | |
| } | |
| void dfs(int x){ | |
| marc[x] = 1; | |
| //printf("{%d}\n",x); | |
| for(int i = 0;i<myv[x].size();i++){ | |
| //printf("%d\n",marc[myv[x][i]]); | |
| if( marc[myv[x][i]] ) ciclo = 1; | |
| else dfs(myv[x][i]); | |
| } | |
| } | |
| int main(){ | |
| scanf("%d %d",&nodes,&edges); | |
| memset(grau,0,sizeof grau); | |
| for(int i = 1;i<=edges;i++){ | |
| int a,b; | |
| scanf("%d %d",&a,&b); | |
| a++; | |
| b++; | |
| myv[a].push_back(b); | |
| grau[b]++; | |
| } | |
| int cont = 0; | |
| size = 0; | |
| for(int i = 1;i<=nodes;i++) if(!grau[i]) heap[++size] = i; | |
| if(size > 0) faz_tudo(); | |
| if(resp.size() == nodes) for(int i = 0;i<resp.size();i++) printf("%d\n",resp[i]); | |
| else printf("*\n"); | |
| return 0; | |
| } |