Huxley 630 - Curso Universitário

A questão parece um problema de ordenação topológica, mas algumas características fazem com que ela seja diferente do algoritmo padrão:

• Existe uma prioridade para cada disciplina. Isso implica que devemos sempre tentar cursar primeiro as disciplinas de maior prioridade;
• Existe uma restrição de quantas disciplinas você pode cursar em um semestre;
• Se a disciplina A é pré-requsito da B, então A e B não podem ser cursadas em um mesmo semestre.

Essas características demandam por adaptações consideráveis nos algoritmos padrão.

ps.: se você ainda não estiver familiarizado com grafos e DFS, olhe o material sobre esses assuntos na página principal e depois resolva essa questão antes: https://www.thehuxley.com/problem/683

Voltando para questão Huxley 630, Eu resolvi assim.

• O problema é modelado como um grafo;
• Cada disciplina é um nó. Cada nó possui vários atributos.
• Como as disciplinas são dadas em ordem de prioridade, então guardo todos os nós em um vector e a ordem do vector já é a prioridade.
• Só que eu inverti as arestas. Ou seja, se C depende de A e B, ao invés de fazer A ->C, B->C, eu fiz: C->A , C->B.
• Depois, rodo um DFS começando pelo primeiro nó da lista de nós. Quando eu chegar em uma folha, adiciono essa folha em um deque. Eu não adiciono os nós intermediários no deque, somente as folhas. Porque se o nó é intermediário, significa que ele ainda depende de alguma disciplina, que deve ser executada em um semestre antes do dele.
• O DFS é chamado para todos os nós ainda não visitados do grafo. Ao terminar, você terá um deque com todas as folhas. Cada folha é uma disciplina em potencial a ser cursada no próximo semestre. Entretanto, qual delas será cursada primeiro? Você ainda precisa ordenar por prioridade.
• Depois de ordenar, é preciso definir quantas serão cursadas naquele semestre. Veja que existem dois casos. O primeiro é quando o número de nós é maior que o número de disciplinas por semestre. Nesse caso, você não irá utilizar todas as disciplinas do seu deque. O segundo caso é quando vc tem menos (ou igual) folhas, nesse caso, usará todas.
• Depois que você usar aquela disciplina no semestre, você precisa marcar esse nó como 'usado'. Assim, você evita utilizar esse nó novamente.
• Agora você vai programar mais um semestre. Marque todos os nós como não visitados, exceto os que você já usou nos semestres anteriores.
• Pronto, agora repita todo o procedimento para pegar uma novo deque com os candidatos para o semestre atual.