1. 

package acm_10044_erdos_numbers;

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: acm_10044_erdos_numbers
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=985
*
* @author Martin Lambeck
* @version 1.0, 10.08.2010
*
* Method : bfs, fast input reader!
* Status : Accepted
* Runtime: 1.144
*/

import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;



public class Main
{
static ErdosReader sc = new ErdosReader();
static HashMap<String, Person> names = new HashMap<String, Person>(10000, 1.0f);
static int tcase = 1;


static List<String> ln = new ArrayList<String>(10000);
static List<Person> lp = new ArrayList<Person>(10000);

public static void main(String[] args) throws IOException
{
int cases = sc.nextInt();

for (int i = 0; i < cases; i++)
testcase();
}

static void testcase() throws IOException
{
int p, n;

names.clear();

p = sc.nextInt();
n = sc.nextInt();

for (int i = 0; i < p; i++)
{
lp.clear();
ln.clear();

String nm;

LinkedList<String> paper = sc.nextPaper();

// there is a non-wellformed input, where the list of authors contains a surname at the end,
// without a first name, ignore this name!!
// http://acm.uva.es/board/viewtopic.php?p=27077#p27077

while (paper.size() > 1)
{
nm = paper.pollFirst() + ", " + paper.pollFirst(); //surname, first name

//System.out.println(nm);


//get person object of this name, if this is not the first occurrence of the person
Person ps = names.get(nm);

if (ps == null)
{
ps = new Person();
names.put(nm, ps);
}

lp.add(ps); //add to list of publishers (person objects)
}

//add the list of publishers, to each publisher
for (Person ps : lp)
ps.neighbors.addAll(lp);
}



//Breadth First Search
//level of node = erdos number

LinkedList<Person> q = new LinkedList<Person>(); //queue

Person erdos = names.get("Erdos, P.");

if (erdos != null)
{
erdos.level = 0;
q.add(erdos);
}

int level = 0; //distance to erdos = erdos number
int neighbors = 0;

while (q.size() > 0)
{
level++;
neighbors = q.size();

Person ps;
Person nb;

for (int i = 0; i < neighbors; i++)
{
ps = q.pollFirst(); //get person from queue

while (ps.neighbors.size() > 0) //iterate thru all neighbors
{
nb = ps.neighbors.pollFirst();

if (nb.level < 0) //not visited before
{
nb.level = level;
q.addLast(nb);
}
}
}
}

System.out.println("Scenario " + tcase);

String name;
Person ps;

for (int i = 0; i < n; i++)
{
name = sc.nextName();
ps = names.get(name);

if (ps == null || (ps.level < 0))
{
System.out.println("" + name + " infinity");
} else
{
System.out.println("" + name + " " + ps.level);
}
}

tcase++;
}

}

class Person
{
LinkedList<Person> neighbors = new LinkedList<Person>();
int level = -1;
}

class ErdosReader
{
InputStream in = new BufferedInputStream(System.in, 32 * 1024);

public String nextName() throws IOException
{
StringBuilder str = new StringBuilder();
int chr;

while (true)
{
chr = in.read();

if (chr == '\n')
{
return str.toString().trim();

} else
{
str.append((char) chr);
}
}
}

public LinkedList<String> nextPaper() throws IOException
{
LinkedList<String> lst = new LinkedList<String>();
StringBuilder str = new StringBuilder();
int chr;
boolean namesDone = false;

while (true)
{
chr = in.read();

if (chr == '\n')
{
return lst;

} else if (!namesDone)
{
if (chr == ':')
{
lst.add(str.toString().trim());
namesDone = true;

} else if (chr == ',')
{
lst.add(str.toString().trim());
str.delete(0, str.length());

} else
{
str.append((char) chr);
}
}
}
}

public int nextInt() throws IOException
{
int num = 0;
int chr;
boolean found = false;

while (true)
{
chr = in.read();

if (chr >= '0' && chr <= '9')
{
num = num*10 + (chr - '0');
found = true;

} else if (found)
{
return num;
}
}
}

}

2.


/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 10044 - Erdos Numbers
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=985
*
* @author Dennis Wilfert
* @version 1.0, 10/22/2009
*
* Method : BFS
* Status : Accepted
* Runtime: 1.068
*/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

class Main {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

// HashMap zum Speichern der Knoten in verbindung mit den Namen
HashMap<String, Node> table = new HashMap<String, Node>();

StringTokenizer token;
int p, n, i, j, k, length, start, end, nodes;
Node u, v, head;
Edge e;
Node[] queue;
String[] line;
String name;

// Anzahl der Szenarios
int scenarios = Integer.parseInt(reader.readLine()) + 1;

for (i = 1; i < scenarios; i++) {
token = new StringTokenizer(reader.readLine());
// Anzahl der Publikationen
p = Integer.parseInt(token.nextToken());
// Anzahl der Namen, dessen Erdös Number berechnet werden soll
n = Integer.parseInt(token.nextToken());

table.clear();
head = new Node();
// Anzahl der Knoten
nodes = 1;
table.put("Erdos, P.", head);

// Namen zu den Publikationen auslesen und zum Graphen hinzufügen
for (j = 0; j < p; j++) {
u = new Node();
nodes++;
line = (reader.readLine().split(":"))[0].split(",");
length = (line.length / 2) * 2;

// Namen zu einer Publikation auslesen und zum Graphen hinzufügen
for (k = 0; k < length; k += 2) {
// Namen richtig formatieren
name = line[k].trim() + "," + line[k + 1];
v = table.get(name);
// Existiert der Name noch nicht wird er neu hinzugefügt
if (v == null) {
v = new Node();
nodes++;
table.put(name, v);
}
u.addEdge(v);
v.addEdge(u);
}
}

// Graphen durchsuchen um die Erdös Number für jeden Namen zu bestimmen.
head.setDistance(0);
queue = new Node[nodes];
start = 0;
end = 1;
queue[0] = head;
while (start < end) {
u = queue[start++];
e = u.getEdge();
while (e != null) {
v = e.getNode();
if (v.getDistance() == -1) {
v.setDistance(u.getDistance() + 1);
queue[end++] = v;
}
e = e.getNext();
}
}

// Ausgabe Schreiben
writer.println("Scenario " + i);
for (j = 0; j < n; j++) {
// Namen lesen, dessen Erdös Number ausgegeben werden sollen
name = reader.readLine().trim();
k = -1;
u = table.get(name);
if (u != null) {
k = u.getDistance();
}
writer.print(name);
writer.println((k == -1) ? " infinity" : " " + (k / 2));
}
}
writer.flush();
}
}

/**
* Die Knoten des Graphen
*
*/
class Node {

private Edge edge;
private int distance;

public void addEdge(Node v) {
edge = new Edge(v, edge);
distance = -1;
}

public Edge getEdge() {
return edge;
}

public void setDistance(int dist) {
this.distance = dist;
}

public int getDistance() {
return distance;
}
}

/**
* Die Kanten des Graphen
*
*/
class Edge {

private final Node node;
private final Edge next;

public Edge(Node node, Edge next) {
this.node = node;
this.next = next;
}

public Node getNode() {
return node;
}

public Edge getNext() {
return next;
}
}