# UVa 10044

Jump to navigation
Jump to search

## Contents

## 10044 - Erdos Numbers[edit]

## Summary[edit]

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[edit]

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[edit]

- 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[edit]

- 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:^{[1]}

- 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[edit]

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

## Input[edit]

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[edit]

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