10044 - Erdos Numbers
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)
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
- 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.
- 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.
- It might be good to use C++ and its STL, because STL containers like vector and string are of dynamic size.
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.
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