Resolução de problemas/Maratona de programação

O problema a seguir é referente à Maratona de Programação – ACM ICPC – 2005 realizada em 10 de setembro de 2005 nas seletivas regionais da América do Sul, etapa Brasil. O problema que será tratado se localiza na página 3 do arquivo que pode ser baixado pelo link Maratona de Programação (pdf).

Problema

Curso Universitário

Há alguns anos atrás, a Universidade de Pinguinhos introduziu um novo sistema flexível de créditos para os alunos ingressantes de cursos de graduação. No novo sistema os alunos podem escolher as disciplinas que desejam cursar em um semestre, com a única restrição de não poderem cursar uma dada disciplina A sem antes terem cursado todas as disciplinas que tiverem sido estabelecidas como pré-requisitos de A. Após alguns semestres o reitor notou que muitos estudantes estavam sendo reprovados em muitas disciplinas, simplesmente porque os estudantes estavam cursando muitas disciplinas por semestre – alguns estudantes chegavam a se matricular em até quinze disciplinas em um semestre. Sendo muito sábio, este ano o reitor introduziu uma regra adicional limitando o número de disciplinas que cada estudante pode cursar por semestre a um certo valor N. Essa regra adicional, no entanto, fez com que os alunos ficassem muito confusos na hora de escolher as disciplinas a serem cursadas em cada semestre. É aí que você entra na estória. O reitor resolveu disponibilizar um programa de computador para ajudar os alunos a fazerem suas escolhas de disciplinas, e solicitou sua ajuda. Mais precisamente, o reitor quer que o programa sugira as disciplinas a serem cursadas durante o curso da seguinte forma. A cada disciplina é atribuída uma prioridade. Se mais do que N disciplinas podem ser cursadas em um determinado semestre (obedecendo ao sistema de pré-requisitos), o programa deve sugerir que o aluno matricule-se nas N disciplinas de maior prioridade. Se N ou menos disciplinas podem ser cursadas em um determinado semestre, o programa deve sugerir que o aluno matricule-se em todas as disciplinas disponíveis. Portanto, dadas a descrição de pré-requisitos para cada disciplina, a prioridade de cada disciplina, e o número máximo de disciplinas por semestre, seu programa deve calcular o número necessário de semestres para concluir o curso, segundo a sugestão do reitor, e a lista de disciplinas que o aluno deve matricular-se em cada semestre.

Entrada

A entrada contém vários casos de teste. Se uma disciplina não tem qualquer pré-requisito ela é denominada básica; caso contrário ela é denominada avançada. A primeira linha de um caso de teste contém dois inteiros 1 • N • 100 e 1 • M • 10 indicando respectivamente o número de disciplinas avançadas do curso e o número máximo de disciplinas que podem ser cursadas por semestre. Cada uma das N linhas seguintes tem o formato

STR0 K STR1 STR2 ... STRK

onde STR0 é o nome de uma disciplina avançada, 1 • K • 15 é o número de disciplinas que são pré-requisitos de STR0, e STR1, STR2, . . . STRK são os nomes das disciplinas que são pré-requisitos de STR0. O nome de uma disciplina é uma cadeia com no mínimo um e no máximo sete caracteres alfanuméricos maiúsculos (‘A’-‘Z’ e ‘0’-‘9’). Note que as disciplinas básicas são aquelas que aparecem apenas como pré-requisito de alguma disciplina avançada. Para concluir o curso, um aluno deve cursar (e passar!) todas as disciplinas básicas e avançadas. A prioridade das disciplinas é determinada pela ordem em que elas aparecem pela primeira vez na entrada: a que aparece primeiro tem maior prioridade, e a que aparece por último tem a menor prioridade. Não há circularidade nos pré-requisitos (ou seja, se a disciplina B tem como pré-requisito a disciplina A então A não tem B como pré-requisito, direta ou indiretamente). O número total de disciplinas é no máximo igual a 200. O final da entrada é indicado por N = M = 0.

A entrada deve ser lida da entrada padrão.

Saída

Para cada caso de teste da entrada seu programa deve produzir a saída na seguinte forma. A primeira linha deve conter a frase ‘Formatura em S semestres’, onde S e o número de semestres necessários para concluir o curso segundo a sugestão do reitor. As S linhas seguintes devem conter a descrição das disciplinas a serem cursadas em cada semestre, um semestre por linha, no formato mostrado no exemplo de saída abaixo. Para cada semestre, a lista das disciplinas deve ser dada em ordem lexicográfica.

Definição: considere as cadeias de caracteres Sa = a1a2...am e Sb = b1b2 . . . bn. Sa precede Sb em ordem lexicográfica se e apenas se Sb é não-vazia e uma das seguintes condições é verdadeira: • Sa é uma cadeia vazia; • a1 < b1 na ordem ‘0’ < ‘1’ < ‘2’ < . . . < ‘9’ < ‘A’ < ‘B’ < . . . < ‘Z’; • a1 = b1 e a cadeia a2a3 . . . am precede a cadeia b2b3 . . . bn.

A saída deve ser escrita na saída padrão.

Apresentado o problema agora vamos a descrição do método de resolução.

Análise do problema

Lendo o segundo parágrafo do problema vê-se que o reitor gostaria que fosse implantado um sistema que sugerisse ao aluno as disciplinas que poderiam ser cursadas a cada semestre obedecendo a um limite e uma prioridade de dependências. Uma disciplina só pode ser cursada se todas as disciplinas das quais ela depende tiverem sido pagas. Utilizando um maior nível de abstração, é fácil de perceber que esse é um problema clássico de ordenação topológica. Para resolvê-lo então se faz necessário uma análise teórica da ordenação topológica.

Teoria

Uma ordenação topológica de um gao (grafo acíclico orientado) G = (V, E) é uma ordenação linear de todos os seus vértices, tal que se G contém uma aresta (u, v), então u aparece antes de v na ordenação. Importante observar que se o grafo não for acíclico não é possível ordenação linear pelo simples motivo da ocorrência de impasses. Por exemplo: Se tivéssemos uma disciplina A que dependa de B que dependa de A, teríamos um deadlock, visto que não se pode pagar a disciplina A sem ter pagado a B e vice-versa. Uma ordenação topológica de um grafo pode ser vista como uma ordenação de seus vértices ao longo de uma linha horizontal, de tal forma que todas as arestas orientadas sigam da esquerda para a direita. O algoritmo de ordenação topológica em pseudocódigo está descrito abaixo:

TOPOLOGICAL-SORT 1 chamar DFS(G) para calcular o tempo de término f[v] para cada vértice v 2 à medida que cada vértice é terminado, inserir o vértice à frente de uma lista ligada 3 return a lista ligada de vértices

Onde DFS é a sigla em inglês para Depth First Search(Busca primeiro na profundidade). O tempo para executar uma ordenação topológica é de (V + E).

Resolução do problema

Dadas a descrição de pré-requisitos para cada disciplina, a prioridade de cada disciplina, e o número máximo de disciplinas por semestre, o programa deve calcular o número necessário de semestres para concluir o curso, segundo a sugestão do reitor, e a lista de disciplinas que o aluno deve matricular-se em cada semestre. Devemos atentar para o fato de a prioridade das disciplinas é determinada pela ordem em que elas aparecem pela primeira vez na entrada: a que aparece primeiro tem maior prioridade, e a que aparece por último tem a menor prioridade. Não há circularidade nos pré-requisitos, ou seja, se a disciplina B tem como pré-requisito a disciplina A então A não tem B como pré-requisito, direta ou indiretamente.

O número máximo de disciplinas em cada caso de teste é de 200.

Primeiramente deve-se definir uma estrutura disciplina que ira me auxiliar na construção do grafo orientado.

typedef struct{ int cod; char name[8]; int grau; bool v; bool ativ; }disciplina;

cód: Rótulo do vértice. Ordem em que a disciplina aparece. Também servirá na análise de prioridade a fim de definir qual disciplina pagar primeiro. name[8]: Nome da disciplina. grau: Número de disciplinas dependentes. v: utilizado como flag na função busca em profundidade pra saber se o vértice já foi visitado. ativ: Depois da busca em profundidade, está flag serve para mostrar se a disciplina já foi incluída na lista de disciplinas pagas por semestre.

disciplina vdisc[MAX]; int adisc[MAX][MAX]; int ndisc;

vdisc: Vetor das disciplinas citadas durante o processo de leitura. adisc: Lista de adjacência das disciplinas. ndisc: Número de disciplinas.

int listadisc[MAX]; int sizelista;

listadisc: Lista parcial das disciplinas que poderão ser pagas no semestre x. sizelista: tamanho da lista.

disciplina semestre[MAX][15]; int discsem[MAX]; int nsemestre;

semestre: Vetor das disciplinas que poderão ser pagas em cada semestre. discsem: vetor que guarda o número de disciplinas por semestre.

int finddisc(char str[8]): Retorna um inteiro maior que zero se a disciplina passada como parâmetro já estiver no grafo. Retorna -1 se a disciplina ainda não for incluída.

void DFS_Visit(int u): Implementa o algoritmo de busca em profundidade e guarda no vetor listadisc todas as disciplinas que são folhas da árvore criada pela busca em profundidade.

bool DFS(): Procedimento principal na busca em profundidade(DFS). Retorna false se todos os vértices já tiverem sido incluídos na listagem das disciplinas por semestre.

ordenar(): Ordena as disciplinas por rótulo em ordem crescente.

ordenar1(): Ordena as disciplinas por ordem alfabética.

int main(): Procedimento principal do programa. Nele está incluso a leitura e impressão dos resultados.

Código completo

#include<iostream>
#include<string.h>

using namespace std;

#define MAX 210

typedef struct{
	int cod;
	char name[8];
	int grau;
	bool v;
	bool ativ;
	bool rem;
}disciplina;

disciplina vdisc[MAX];
int adisc[MAX][MAX];
int ndisc;

int listadisc[MAX];
int sizelista;

disciplina semestre[MAX][15];
int discsem[MAX];
int nsemestre;

int finddisc(char str[8]){
	for(int i=0;i<ndisc;i++){
      if( strcmp(str, vdisc[i].name) == 0 ){
			return i;
		}
	}
	return -1;
}

void DFS_Visit(int u){
	bool depend = false;
	vdisc[u].v = true;

	for(int i=0;i<vdisc[u].grau;i++){
		if(vdisc[adisc[u][i]].ativ)
			depend = true;
		
		if(!vdisc[adisc[u][i]].v && vdisc[adisc[u][i]].ativ){
			DFS_Visit(adisc[u][i]);
		}
	}

	if(!depend){
		vdisc[u].rem = true;
		listadisc[sizelista] = u;
		sizelista++;
	}
}

bool DFS(){
	bool thereway = false;
	for(int i=0;i<ndisc;i++){
		vdisc[i].v = false;
	}
	for(int i=0;i<ndisc;i++){
		if(!vdisc[i].v && vdisc[i].ativ){
			thereway = true;
			DFS_Visit(i);
		}
	}
	return thereway;
}

void ordenar(){
	int tmp;
	for(int i=0;i<sizelista-1;i++){
		for(int j=i+1;j<sizelista;j++){
			if(listadisc[i]>listadisc[j]){
				tmp = listadisc[i];
				listadisc[i] = listadisc[j];
				listadisc[j] = tmp;
			}
		}
	}
}

void ordenar1(int n){
	disciplina tmp;
	for(int i=0;i<discsem[n]-1;i++){
		for(int j=i;j<discsem[n];j++){
			if(strcmp(semestre[n][i].name, semestre[n][j].name) > 0){
				tmp = semestre[n][i];
				semestre[n][i] = semestre[n][j];
				semestre[n][j] = tmp;
			}
		}
	}
}

int main(){

	int n, m;
	int k;
	char strdisc[8];
	int posdisc;
	int posdep;

	while(true){
	
		cin>>n>>m;
		if(n == 0 && m == 0)
			break;

		ndisc = 0;
		for(int i=0;i<MAX;i++){
			vdisc[i].cod = i;
			vdisc[i].name[0] = '\0';
			vdisc[i].grau = 0;
			vdisc[i].ativ = true;
			vdisc[i].rem = false;
		}

		for(int i=0;i<n;i++){
			cin>>strdisc;
			posdisc = finddisc(strdisc);
			if(posdisc == -1){
				strcpy(vdisc[ndisc].name,strdisc);
				posdisc = ndisc;
				++ndisc;
			}			
			cin>>k;
			for(int j=0;j<k;j++){
				cin>>strdisc;
				posdep = finddisc(strdisc);
				if(posdep == -1){
					strcpy(vdisc[ndisc].name,strdisc);
					posdep = ndisc;
					++ndisc;
				}
				adisc[posdisc][vdisc[posdisc].grau] = posdep;
				vdisc[posdisc].grau++;
			}
		}

		nsemestre = 0;
		while(true){
			sizelista = 0;
			if(!DFS())
				break;
			ordenar();

			discsem[nsemestre] = (m<sizelista)?m:sizelista;
			
			for(int i=0;i<m;i++){
				if(i<sizelista){
					vdisc[listadisc[i]].ativ = false;
					semestre[nsemestre][i] = vdisc[listadisc[i]];
				}
			}

			ordenar1(nsemestre);

			nsemestre++;
		}

		cout<<"Formatura em "<<nsemestre<<" semestres"<<endl;
		for(int i=0;i<nsemestre;i++){
			cout<<"Semestre "<<i+1<<" :";
			for(int j=0;j<discsem[i];j++){
				cout<<" "<<semestre[i][j].name;
			}
			cout<<endl;
		}

	}

	return 0;
}