UVa 10044

10044 - Erdos Numbers

• http://acm.uva.es/p/v100/10044.html

Summary

Given a set of research papers and names of the authors, calculate the "collaborative distance" between people and the Hungarian mathematician Paul Erdős.
(Read Wikipedia for more background information: Erdős Number)

Explanation

1. Build an adjacency list or adjacency matrix based on the paper database
2. Perform Breadth-First Search (take "Erdos, P." as root) and store the distance

Gotchas

• Be careful with name parsing. Space or whatever ASCII character might appear before or after the names.
• The queries strictly follows the name format but in the database there might be authors with only last-name given. Do not expect that last-names and first-names always come in pairs.
• To avoid TLE, make sure your program will not re-visit nodes during the Breadth-First Search.

Notes

• The input size (e.g. length of the names, number of distinct names, etc.) is not specified clearly in the problem statement.
  According to the discussion on the UVa discussion board:
  - maximal number of different persons in all papers together of one scenario is less than 5001
  - maximal length of input lines is less than 10001
  - maximal length of person names is less than 101
  - maximal number of links from one person to others is less than 501
• The title of the research papers are of no uses at all, hence need not to be stored.

Implementations

• It might be good to use C++ and its STL, because STL containers like vector and string are of dynamic size.

Input

3
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.
5 7
Pang, P., Lee, C.H.: a paper
Pang, P., Lui, S.H.: another paper
Ng, G., Chan, S.: sth
Pang, P., Ng, G.: sth new
Chan, S., Erdos, P.: sth old
Pang, P.
Lee, C.H.
Ng, G.
Chan, S.
Lui, S.H.
Erdos, P.
Tse, C.
5 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., Johnson: Introduction to Algorithms
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.

Output

Scenario 1
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2
Scenario 2
Pang, P. 3
Lee, C.H. 4
Ng, G. 2
Chan, S. 1
Lui, S.H. 4
Erdos, P. 0
Tse, C. infinity
Scenario 3
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2