Aula por Lucca Siaudzionis
"Malter Warinho está ensinando seu filho a se vestir. Para isso, está dando instruções simples sobre a ordem em que seu filho deve se vestir, para não colocar a roupa em ordem contrária (tipo o Superman). As instruções são do tipo: as meias devem ser colocadas antes do sapatos; as calças devem ser vestidas antes do cinto; a camisa deve ser vestida antes do casaco; e por aí vai. Em alguns casos, não interessa a ordem em que deve ser colocada a roupa, por exemplo, o filho pode colocar as calças antes do chapéu e vice-versa. Dada a lista de instruções e o número de peças de roupas, ajude o filho de Malter a se vestir."
Bem, para formalizar um pouco o problema, vamos montar um grafo direcionado onde:
- cada vértice é uma peça de roupa.
- cada aresta partindo de um vértice
para um vértice 
significa que tem que vir antes de .
Assim, pode se notar uma relação de transição: se tem que vir antes de e tem que vir antes de 
, tem que vir antes de .
Teremos então um grafo semelhante a este:
Tendo uma noção do grafo, é fácil perceber alguns fatos simples:
- se o grafo possui um ciclo, não há ordem em que se possa resolver o problema.
- podemos executar um vértice (vestir uma roupa) se, e somente se, todos os vértices (roupas) que possuem algum caminho até ele já foram executados.
Com apenas isso, já se pode pensar em um algoritmo bem simples para resolver o problema:
- Pegar um vértice de grau de entrada zero (nenhuma aresta chega a ele) e acrescentar o vértice a ordem de execução.
- Remover todas as arestas que partem desse vértice e atualizar os graus dos vértices ligados a essas arestas.
- Repetir o processo até não haver mais vértices de grau de entrada zero (ou acabarem todos os vértices).
Se, ao final do processo, ainda sobrarem vértices, há um ciclo e não há ordem para resolver o problema. Caso contrário, o problema está resolvido!
Vamos simular o algoritmo para o grafo anterior.
De início, existem quatro vértices de grau zero na lista: 
, 
, 
e 
. Vamos começar pelo .
 |
Vértice | Grau |
|
 |
|
 |
|
|
|
|
|
|
|
|
 |
|
|
 |
|
|
 |
|
|
|
|
Removendo o , atualizamos o grau do vértice . O próximo a ser selecionado que possui grau zero é o .
 |
Vértice | Grau |
|
 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Removendo o , faremos o vértice passar a ter grau zero e o acrescentamos a nossa lista de vértices de grau zero. O próximo vértice na lista é o .
 |
Vértice | Grau |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Remover o vértice não altera nada, pois não existem mais arestas partindo desse vértice. O próximo vértice na lista é o .
 |
Vértice | Grau |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ao remover o , faremos o vértice ter grau zero e, portanto, o acrescentamos a lista. O próximo vértice é o .
 |
Vértice | Grau |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ao remover o , fazemos o vértice ter grau zero e, portanto, o acrescentamos a lista. O próximo vértice é o .
 |
Vértice | Grau |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ao remover o , faremos restar apenas vértices de grau zero no grafo, portanto, podemos removê-los em qualquer ordem.
Finalizando, temos as seguinte ordem de remoção de vértices (execução de tarefas): 
.
Um código para resolver o problema do Filho de Malter, em C++, seria:
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
| // | |
| // filho_de_malter.cpp | |
| // | |
| // Created by Lucca Siaudzionis on 07/08/15. | |
| // | |
| // Filho de Malter - Noic | |
| #include <cstdio> | |
| #include <vector> | |
| using namespace std; | |
| //------------------------------ | |
| #define MAXN 100100 | |
| int n; // número de vértices | |
| int m; // número de arestas | |
| vector<int> grafo[MAXN]; | |
| int grau[MAXN]; | |
| vector<int> lista; // dos vértices de grau zero | |
| //------------------------------ | |
| int main(){ | |
| scanf("%d %d", &n, &m); | |
| for(int i = 1;i <= m;i++){ | |
| int x, y; | |
| scanf("%d %d", &x, &y); | |
| // tarefa X tem que ser executada antes da tarefa Y | |
| grau[y]++; | |
| grafo[x].push_back(y); | |
| } | |
| for(int i = 1;i <= n;i++) if(grau[i] == 0) lista.push_back(i); | |
| // o procedimento a ser feito é semelhante a uma BFS | |
| int ini = 0; | |
| while(ini < (int)lista.size()){ | |
| int atual = lista[ini]; | |
| ini++; | |
| for(int i = 0;i < (int)grafo[atual].size();i++){ | |
| int v = grafo[atual][i]; | |
| grau[v]--; | |
| if(grau[v] == 0) lista.push_back(v); // se o grau se tornar zero, acrescenta-se a lista | |
| } | |
| } | |
| // agora, se na lista não houver N vértices, | |
| // sabemos que é impossível realizar o procedimento | |
| if((int)lista.size() < n) printf("impossivel\n"); | |
| else{ | |
| for(int i = 0;i < (int)lista.size();i++) printf("%d ", lista[i]); | |
| printf("\n"); | |
| } | |
| return 0; | |
| } |
Agora, para praticar, resolva os seguintes problemas.
Problema 1 - A Base de um Gráfico
Problema 2 - Escalonamento Ótimo
Problema 3 - Ordering Tasks
As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.