2013-02-23 21:59:11Morris
[UVA][字串處理][bfs] 10044 - Erdos Numbers
Problem F: Erdös Numbers
| Problem F: Erdös Numbers |
Background
The Hungarian Paul Erdös (1913-1996, speak as ``Ar-dish'') not only was one of the strangest mathematicians of the 20th century, he was also one of the most famous. He kept on publishing widely circulated papers up to a very high age and every mathematician having the honor of being a co-author to Erdös is well respected.Not everybody got the chance to co-author a paper with Erdös, so many people were content if they managed to publish a paper with somebody who had published a scientific paper with Erdös. This gave rise to the so-called Erdös numbers. An author who has jointly published with Erdös had Erdös number 1. An author who had not published with Erdös but with somebody with Erdös number 1 obtained Erdös number 2, and so on.
Problem
Today, nearly everybody wants to know which Erdös number he or she has. Your task is to write a program which computes Erdös numbers for a given set of scientists.
Input
The first line of the input contains the number of scenarios.The input for each scenario consists of a paper database and a list of names. It begins with the line
P N
where P and N are natural numbers. Following this line are P lines containing descriptions of papers (this is the paper database). A paper appears on a line by itself and is specified in the following way:
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors matricesNote that umlauts like `ö' are simply written as `o'. After the P papers follow N lines with names. Such a name line has the following format:
Martin, G.
Output
For every scenario you are to print a line containing a string ``Scenario i" (where i is the number of the scenario) and the author names together with their Erdös number of all authors in the list of names. The authors should appear in the same order as they appear in the list of names. The Erdös number is based on the papers in the paper database of this scenario. Authors which do not have any relation to Erdös via the papers in the database have Erdös number ``infinity".
Sample Input
1 4 3 Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factor matrices Erdos, P., Reisig, W.: Stuttering in petri nets Smith, M.N., Chen, X.: First oder derivates in structured programming Jablonski, T., Hsueh, Z.: Selfstabilizing data structures Smith, M.N. Hsueh, Z. Chen, X.
Sample Output
Scenario 1 Smith, M.N. 1 Hsueh, Z. infinity Chen, X. 2
// 0.060 s by morris821028
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
using namespace std;
char s[100005];
int main() {
int t, cases = 0;
int n, m, i, j;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
while(getchar() != '\n');
map<string, int> name;
map<string, int>::iterator it;
vector<short> g[5005];
int buf[5005];
name["Erdos, P."] = 0;
int name_size = 0;
while(n--) {
gets(s);
int pre_idx = 0, bidx = 0;
for(i = 1; s[i]; i++) {
if((s[i] == ',' || s[i] == ':') && s[i-1] == '.') {
char tmp = s[i];
s[i] = '\0';
it = name.find(s+pre_idx);
if(it == name.end()) {
name[s+pre_idx] = ++name_size;
buf[bidx++] = name_size;
} else {
buf[bidx++] = it->second;
}
s[i] = tmp;
pre_idx = i+2;
if(s[i] == ':')
break;
}
}
for(i = 0; i < bidx; i++) {
for(j = i+1; j < bidx; j++) {
g[buf[i]].push_back(buf[j]);
g[buf[j]].push_back(buf[i]);
}
}
}
int used[5005] = {}, dp[5005] = {}, x;
used[0] = 1, dp[0] = 0;
queue<int> Q;
Q.push(0);
while(!Q.empty()) {
x = Q.front(), Q.pop();
for(vector<short>::iterator it = g[x].begin();
it != g[x].end(); it++) {
if(used[*it] == 0) {
dp[*it] = dp[x]+1;
used[*it] = 1;
Q.push(*it);
}
}
}
printf("Scenario %d\n", ++cases);
while(m--) {
gets(s);
it = name.find(s);
printf("%s ", s);
if(it == name.end())
puts("infinity");
else if(!used[it->second])
puts("infinity");
else
printf("%d\n", dp[it->second]); }
}
return 0;
}