Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2249
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2249
Erdos Number
By OBI - Olimpíada Brasileira de Informática 2003 
Brazil
Timelimit: 1
The Hungarian mathematician Paul Erdos (1913-1996), one of the brightest of the twentieth century, is considered the most prolific mathematician in history. Erdos published over 1500 articles, in collaboration with about 450 other mathematicians. In honor of this Hungarian genius, mathematicians created a number called "number of Erdos." Every person who wrote a paper with Erdos has the number 1. All that do not have number 1, but wrote an article with someone who has number 1, have number 2. And so on. When no connection can be established between Erdos and a person, it is said that it has infinite number of Erdos. For example, the number of Erdos Albert Einstein is 2. And, perhaps surprisingly, the number of Erdos Bill Gates is 4.
Your task is to write a program that, from a list of authors of articles, determine the number of Erdos authors.
Input
The input consists of several test sets. The first line of a test set contains an integer A (1 ≤ A ≤ 100),indicating the number of articles. Each one of A the following lines contain the list of authors of an article. Each author is identified by the initial of his name (capitalized), followed by a point and a blank (indicating that the name is abbreviated), followed by his/her last name (‘P. Erdos’, for example). The last name of an author has a maximum of 15 letters, and only the first letter appears in uppercase. The authors are separated by commas, and the list of authors of an article ends with a point (see the examples below). A single white space separates the name abbreviation of the last name and the name of the previous author. Blanks are not used elsewhere. An article has a maximum of 10 authors, and the total of authors does not exceed 100. The end of entry is indicated by A = 0.
Output
For each input set of test his program to produce a set of rows in the output. The first line should contain a test set identifier in the format "Teste n", where n is sequentially numbered from 1. The following should appear a line for each & nbsp; author of set of tests (except the very P. Erdos ). Each line should contain the author's name followed by the character ':', a blank space and the number of Erdos. If the number of Erdos of a particular author is infinite, type 'infinito'. The output should be ordered alphabetically by author's last name, and if the same last name, the tie should be done by the initial of the first name. Print a blank line at the end of each test set. The spelling shown in Output Sample below should be followed strictly.
| Input Sample | Output Sample |
|
5 P. Erdos, A. Selberg. P. Erdos, J. Silva, M. Souza. M. Souza, A. Selberg, A. Oliveira. J. Ninguem, M. Ninguem. P. Duarte, A. Oliveira. 2 Z. Silva, P. Erdos. Z. Souza. 0 |
Teste 1 P. Duarte: 3 J. Ninguem: infinito M. Ninguem: infinito A. Oliveira: 2 A. Selberg: 1 J. Silva: 1 M. Souza: 1 Teste 2 Z. Silva: 1 Z. Souza: infinito |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define true 1
#define false 0
#define INF 0x3f3f
typedef struct{
char nome[20];
unsigned erdos;
} autor_t;
char grid[101][101];
autor_t autores[101];
unsigned autores_n, artigos_n, tmp = 1;
void ascan();
void erdos_n();
void imprime();
int idx_a(char *);
int compara(autor_t *, autor_t *);
int main(int argc, char **argv)
{
while (scanf("%u", &artigos_n), artigos_n)
{
autores_n = 0;
memset(grid, 0,sizeof(grid));
while (artigos_n--)
ascan();
erdos_n();
imprime();
}
return 0;
}
void ascan()
{
char nome[20];
int n, i, j, out, autores_i[10];
n = 0;
do
{
scanf("%s %s", nome, &nome[3]);
nome[2] = ' ';
out = nome[strlen(nome) - 1] == '.';
nome[strlen(nome) - 1] = '\0';
autores_i[n++] = idx_a(nome);
} while (!out);
for (i = 0; i < n; ++i)
for (j = i + 1; j < n; ++j)
grid[autores_i[i]][autores_i[j]] = grid[autores_i[j]][autores_i[i]] = true;
}
void erdos_n()
{
int fila[101], fila_i = 0, fila_f = 1, i, j;
fila[0] = idx_a("P. Erdos");
autores[fila[0]].erdos = 0;
while (fila_f > fila_i)
{
i = fila[fila_i++];
for (j = 0; j < autores_n; ++j)
if (grid[i][j] && autores[j].erdos == INF)
autores[j].erdos = autores[i].erdos + 1, fila[fila_f++] = j;
}
}
int idx_a(char *nome)
{
int i;
for (i = 0; i < autores_n; ++i)
if (strcmp(nome, autores[i].nome) == 0)
return i;
strcpy(autores[autores_n].nome, nome);
autores[autores_n].erdos = INF;
return autores_n++;
}
void imprime()
{
int i;
printf("Teste %u\n", tmp++);
for (i = 0; i < autores_n; ++i)
if (strcmp(autores[i].nome, "P. Erdos") != 0)
if (autores[i].erdos == INF)
printf("%s: infinito\n", autores[i].nome);
printf("\n");
}
int compara(autor_t *a, autor_t *b)
{
int ans;
if ((ans = strcmp(&(a->nome[3]), &(b->nome[3]))) != 0)
return ans;
return a->nome[0] - b->nome[0];
}
Input
P. Erdos, A. Selberg.
P. Erdos, J. Silva, M. Souza.
M. Souza, A. Selberg, A. Oliveira.
J. Ninguem, M. Ninguem.
P. Duarte, A. Oliveira.
2
Z. Silva, P. Erdos.
Z. Souza.
0
Output
P. Duarte: 3
J. Ninguem: infinito
M. Ninguem: infinito
A. Oliveira: 2
A. Selberg: 1
J. Silva: 1
M. Souza: 1
Teste 2
Z. Silva: 1
Z. Souza: infinito
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#define MAXN 110
#define MP make_pair
#define endl '\n'
using namespace std;
typedef pair < string, string> pss;
typedef set<int> si;
typedef pair < int, int> ii;
int nivel[MAXN];
si grafo[MAXN];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int artigos, teste = 1;
while (cin >> artigos && artigos) {
map < pss, int> mapa;
int contador = 0;
string inicialerdos = "P.", nomeerdos = "Erdos";
mapa[MP(nomeerdos, inicialerdos)] = 0;
grafo[0].clear();
while (artigos--) {
string inicial, nome;
si autores;
bool condicional = false;
while (!condicional) {
cin >> inicial >> nome;
string::iterator it = --nome.end();
condicional = *(it) == '.';
nome.erase(it);
pss nomecompleto = MP(nome, inicial);
if (mapa.find(nomecompleto) == mapa.end()) {
mapa[nomecompleto] = ++contador;
nivel[contador] = -1;
grafo[contador].clear();
}
autores.insert(mapa[nomecompleto]);
}
for (si::iterator i = autores.begin(); i != autores.end(); i++)
for (si::iterator j = autores.begin(); j != autores.end();
j++) {
grafo[*i].insert(*j);
grafo[*j].insert(*i);
}
}
for (int i = 0; i < = contador; i++) grafo[i].erase(i);
priority_queue < ii, vector<ii>, greater > fila;
nivel[0] = -1;
fila.push(MP(0, 0));
while (!fila.empty()) {
ii davez = fila.top();
fila.pop();
int distancia = davez.first, vertice = davez.second;
if (nivel[vertice] != -1) continue;
nivel[vertice] = distancia;
for (si::iterator i = grafo[vertice].begin();
i != grafo[vertice].end(); i++)
if (nivel[*i] == -1) fila.push(MP(distancia + 1, *i));
}
mapa.erase(MP(nomeerdos, inicialerdos));
cout << "Teste " << teste++ << endl;
for (map < pss, int>::iterator percorrer = mapa.begin();
percorrer != mapa.end(); percorrer++) {
cout << (*(percorrer)).first.second << " "
<< (*(percorrer)).first.first << ": ";
if (nivel[(*(percorrer)).second] == -1)
cout << "infinito" << endl;
else
cout << nivel[(*(percorrer)).second] << endl;
}
cout << endl;
}
return 0;
}
Input
P. Erdos, A. Selberg.
P. Erdos, J. Silva, M. Souza.
M. Souza, A. Selberg, A. Oliveira.
J. Ninguem, M. Ninguem.
P. Duarte, A. Oliveira.
2
Z. Silva, P. Erdos.
Z. Souza.
0
Output
P. Duarte: 3
J. Ninguem: infinito
M. Ninguem: infinito
A. Oliveira: 2
A. Selberg: 1
J. Silva: 1
M. Souza: 1
Teste 2
Z. Silva: 1
Z. Souza: infinito