#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/***************************************************************************
Class Sorter

Read in a list of classes and their prerequisites. Each line is of the form
	<class> : <pre1> <pre2> ...
for some number of prerequisites (possibly 0). Print out the order in which
the classes must be taken, so that the prerequisite requirement is satisfied.
If two classes could be taken at the same time, take the one with the lowest
number first; if the numbers match, take the one with the alphabetically
highest department first.
***************************************************************************/

#define NUM 100    /* maximum number of classes */
#define MAX 80     /* maximum line length */
#define NAME 8     /* maximum length of a class name */

void initialize(char pre[NUM][NUM], int *count);
void add_class(char line[MAX], char pre[NUM][NUM], char name[NUM][NAME+1],
	int *count);
int get_word(char line[MAX], char temp[MAX], int *i);
int valid(char c);
int name_lookup(char temp[MAX], char name[NUM][NAME+1], int *count);
void top_sort(char name[NUM][NAME+1], char pre[NUM][NUM], int count);
int compare(char a[], char b[]);
int number(char name[]);

/***************************************************************************
main
***************************************************************************/
void main(void)
{
char pre[NUM][NUM];
char name[NUM][NAME+1];
char line[MAX];
int count;
int set = 0;
char *ret;

initialize(pre, &count);
do {
	ret = gets(line);
	if (strlen(line) > 0)
		{
		/* Add this class and its prerequisites. */
		add_class(line, pre, name, &count);
		}
	else if (count > 0)
		{
		printf("Dataset %d:\n", set+1);
		set ++;
		/* We should perform the topological sort and print the output. */
		top_sort(name, pre, count);
		printf("\n");
		/* Reinitialize. */
		initialize(pre, &count);
		}
	} while (ret);
}

/***************************************************************************
initialize
***************************************************************************/
void initialize(char pre[NUM][NUM], int *count)
{
int i, j;

for (i = 0; i < NUM; i++)
	for (j = 0; j < NUM; j++)
		pre[i][j] = 0;
*count = 0;
}

/***************************************************************************
add_class
***************************************************************************/
void add_class(char line[MAX], char pre[NUM][NUM], char name[NUM][NAME+1],
	int *count)
{
char temp[MAX];
int i = 0;
int c, k;

/* Get the name of the class. Look it up in the list of names. If it is not
   found, then add it. */
get_word(line, temp, &i);
c = name_lookup(temp, name, count);

/* Read all the prerequisites and update the array. */
while (get_word(line, temp, &i))
	{
	k = name_lookup(temp, name, count);
	pre[c][k] = 1;
	}
}

/***************************************************************************
get_word

Extracts the next word from line. <i> indicates where to start. After reading
the word, <i> is changed to the end of the word for the next reading.
***************************************************************************/
int get_word(char line[MAX], char temp[MAX], int *i)
{
int j = 0;

/* Skip white space. If the end of the line is found, return that no word was
   read. */
while (! valid(line[*i]))
	{
	if (line[*i] == 0)
		return 0;
	(*i) ++;
	}

/* Copy the word. */
while (valid(line[*i]))
	{
	temp[j] = line[*i];
	j ++;
	(*i) ++;
	}

/* Terminate the copied word correctly and return that a word was found. */
temp[j] = 0;
return 1;
}

/***************************************************************************
valid

Return 1 iff the character is an uppercase letter or a numeral.
***************************************************************************/
int valid(char c)
{
if (('A' <= c) && (c <= 'Z'))
	return 1;
if (('0' <= c) && (c <= '9'))
	return 1;
return 0;
}

/***************************************************************************
name_lookup

Return the location of <temp> in the list <name>. If <temp> does not occur,
then add it and return the new location.
***************************************************************************/
int name_lookup(char temp[MAX], char name[NUM][NAME+1], int *count)
{
int i;

/* Check if temp occurs in the list of names. */
for (i = 0; i < *count; i++)
	if (strcmp(temp, name[i]) == 0)
		return i;

/* It doesn't occur. Add it. */
strcpy(name[*count], temp);
(*count) ++;
return (*count) - 1;
}

/***************************************************************************
top_sort

Perform the topological sort. If two classes have no unsatisfied prerequisites,
then take the one that has the lowest number; if the numbers are the same, take
the one with the alphabetically lowest department. If a cycle is detected,
print that out.
***************************************************************************/
void top_sort(char name[NUM][NAME+1], char pre[NUM][NUM], int count)
{
char used[NUM];   /* flag indicating whether class has been printed by sort */
int total[NUM];   /* total number of prerequisites that a class has */
int order[NUM];   /* Order that classes are printed out. */
int i, j, k;

/* Initialize that all classes are un-used, and count total number of
   prerequisites for each class. */
for (i = 0; i < count; i++)
	{
	used[i] = 0;
	total[i] = 0;
	for (j = 0; j < count; j++)
		if (pre[i][j])
			total[i] ++;
	}

/* Perform topological sort. */
for (i = 0; i < count; i++)
	{
	k = -1;
	for (j = 0; j < count; j++)
		if (!used[j] && (total[j] == 0))
			{
			/* Class j has no unsatisfied prerequisites. */
			if (k == -1)
				/* We have not found a class yet with no unsatisfied prereqs. */
				k = j;
			else
				/* We have found another class with no unsatisfied prereqs.
				   Keep the class with the lowest number, or if numbers are
				   the same, alphabetically lowest department. */
				{
				if (compare(name[k], name[j]) == 1)
					k = j;
				}
			}
	if (k == -1)
		{
		/* There is no class with unsatisfied prereqs. Must be a cycle. */
		printf("A cycle was detected in the classes.\n");
		return;
		}
	/* Mark class k as used, and remove it from the array of prereqs. */
	used[k] = 1;
	for (j = 0; j < count; j++)
		if (pre[j][k])
			{
			pre[j][k] = 0;
			total[j] --;
			}
	/* We'll eventually print out this class next. */
	order[i] = k;
	}

/* No cycles were detected. Print out the classes in order. */
for (i = 0; i < count; i++)
	printf("%3d: %s\n", i+1, name[order[i]]);
}

/***************************************************************************
compare

Returns -1 if a < b, 0 if a == b, and 1 if a > b. The order is defined by
first comparing the number part of the class names; if they're equal, compare
the department part.
***************************************************************************/
int compare(char a[], char b[])
{
int na, nb;

na = number(a);
nb = number(b);
if (na < nb)
	return -1;
if (na > nb)
	return 1;
return strcmp(a, b);
}

/***************************************************************************
number

Returns the number portion of a class's name.
***************************************************************************/
int number(char name[])
{
int i = 0;

while (('A' <= name[i]) && (name[i] <= 'Z'))
	i ++;
return atoi(name + i);
}