[UVA] 925 - No more prerequisites, please!
No moreprerequisites, please!
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...
Problem
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.
Input
The first line contains the number C of test cases that follow ( 0 < C < 1000 ).
Each test case starts with a line containing 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 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).
Output
For each input case your program must output the information about the 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.
Within each test case, the courses must be listed ordered by name, and the list of prerequisites for each course must also be ordered by course name.
Sample Input
2
5
cc
ca
ce
cb
cd
3
ce 4 cd cb cc ca
cd 3 cb cc ca
cb 1 ca
9
dg
di
dc
df
de
dd
da
dh
db
7
dg 3 da de df
dd 2 da db
df 1 de
dc 1 db
dh 5 da de dg df dc
de 2 da dd
di 2 df dd
Sample Output
cb 1 ca
cd 2 cb cc
ce 1 cd
dc 1 db
dd 2 da db
de 1 dd
df 1 de
dg 1 df
dh 2 dc dg
di 1 df
MIUP'2004:Fourth Portuguese National Programming Contest
Problem setter: Isabel Nunes
題目描述：
修課的時候常會有必須先修過哪些，否則會擋修。然而有些條件會重覆，也就是 A->B->C，
要修 C 前必須修過 A, B，不過事實上只要"說明"修過 B 即可。
題目即是想要找道每一門修的最少條件。
題目解法：
建圖找最短路徑，倒不如說是找可連性。對於 C 而言，如果 B->C, A->B, 則最後忽略 A。
把所有可能被忽略的情況找一次，最後輸出不能忽略的幾個。
#include <stdio.h>
#include <string.h>
#include <map>
#include <iostream>
using namespace std;
int main() {
int n, m, q;
char s[105];
int g[150][150];
int i, j, k;
int testcase;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
map<string, int> R;
string rR[150];
for(i = 0; i < n; i++) {
scanf("%s", s);
R[s] = i;
}
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
g[i][j] = 0;
int n = 0;
for(map<string, int>::iterator it = R.begin();
it != R.end(); it++) {
it->second = ++n;
rR[n] = it->first;
}
scanf("%d", &m);
while(m--) {
scanf("%s %d", s, &q);
int x = R[s];
while(q--) {
scanf("%s", s);
int y = R[s];
g[x][y] = 1;
}
}
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
g[i][j] |= g[i][k]&g[k][j];
for(i = 1; i <= n; i++) {
int mark[150] = {};
for(j = 1; j <= n; j++) {
if(g[i][j]) {
for(k = 1; k <= n; k++) {
if(g[k][j] && g[i][k]) {
mark[j] = 1;
break;
}
}
}
}
int p = 0;
for(j = 1; j <= n; j++)
if(g[i][j] && mark[j] == 0)
p++;
if(p > 0) {
printf("%s %d", rR[i].c_str(), p);
for(j = 1; j <= n; j++)
if(g[i][j] && mark[j] == 0)
printf(" %s", rR[j].c_str());
puts("");
}
}
}
return 0;
}