Recently, I had to prepare a small students guide concerning our Computer Science graduation. I asked all my colleagues to send me some specific pieces of information about the courses they were responsible for. One of these pieces of information was the set of prerequisites that is defined for each course c, that is, the set of courses that the student is supposed to have completed before he can attend course c.
Some of my colleagues were so zealous of their task that they sent me more information than I needed... I'll explain:
Let ca, cb,
cc, cd and ce be courses of our Computer Science
graduation.
Suppose ca is a prerequisite for cb; cb and cc
are prerequisites for cd; cd is a prerequisite for ce.
John, who is responsible for course cd, told me that the prerequisites
for cd were cc, cb and ca;
Elizabeth, who is responsible for course ce, told me that the
prerequisites for ce were cd, cc, cb and ca.
But I only needed prerequisites cc and cb for course cd because cb already has ca as its prerequisite! Likewise, I only needed prerequisite cd for course ce because cd already has cc, cb, and ca as its prerequisites!
Unfortunately, not all my colleagues asked me whether I wanted the whole set of prerequisites or the minimum one; they asked John instead!! He told them that “the most information, the better”!
I had no courage to tell them that, by sending me more information than the one I needed, they were turning my task of gathering all their info more difficult. How I wished for some robot that I could feed with the information I had, and that gave me, for each course, the minimum set of prerequisites!
Never too late...
Your task consists of writing a program that, given the name and prerequisites of a set of courses, computes the minimum set of prerequisites for all courses.
The first line contains the number k (0 < k <= 120) of courses that are to be processed. The next k lines contain the names of the k courses, one per line. The next line (the k+2th line) contains the number j of courses that have prerequisites (0 <= j <= 120). The next j lines contain, for each course that has some prerequisite, the course name, the number of prerequisites it has, and the names of the courses that are its prerequisites, separated by a single space.
Course names have maximum length 20, do not contain any spaces, and are composed of characters in the set {‘a’..‘z’}.
There are no cycles on prerequisites, that is, it is never the case that some course c has a prerequisite course cp that has c as a prerequisite (directly or indirectly).
The output file must have j lines containing information about the j courses that have prerequisites. Each line must contain the name of the course, the number of prerequisites it has, and the names of the courses that are its prerequisites, separated by a single space.
The courses must be listed ordered by name, and the list of prerequisites for each course must also be ordered by course name.
5
cc
ca
cecbcd3ce 4 cd cb cc cacd 3 cb cc cacb 1 ca
cb 1 ca
cd 2 cb cc
ce 1 cd
MIUP’2004: Fourth Portuguese National
Programming Contest