Erdos Number (UVA 10044).

erdos.py

import sys

DEBUG       = True
INFINITY    = 99999

def debug(var):
    if DEBUG:
        sys.stderr.write(repr(var) + "\n")

def make_adjacent(graph, people, paper):
    paper = filter(lambda p : p != people, paper)
    for p in paper:
        graph[people].append(p)

def BFS(graph, source):
    distance = {}
    visited = {}
    queue = []
    for author in graph.keys():
        distance[author] = INFINITY
    distance[source] = 0
    queue.append(source)
    while queue:
        v = queue.pop()
        visited[v] = True
        neighbor = filter(lambda n : not visited.get(n), \
                graph.get(v))
        for n in neighbor:
            visited[n] = True
            distance[n] = min(distance[n], distance[v] + 1)
            queue.append(n)
    return distance

def solve(papers):
    graph = {}
    for paper in papers:
        for people in paper:
            if not graph.get(people):
                graph[people] = []
            make_adjacent(graph, people, paper)
    return BFS(graph, "Erdos, P.")

def main():
    N = int(sys.stdin.readline())
    for problem in range(N):
        line = sys.stdin.readline()
        npapers, nscenarios = map(int, line.split(" "))
        papers = []
        for p in range(npapers):
            line = sys.stdin.readline()
            trimmed = line.split(".:")[0]
            authors = map(lambda s : s + ".",\
                    trimmed.split("., "))
            papers.append([a for a in authors])

        erdos_number = solve(papers)
        sys.stdout.write("Scenario " + repr(N) + "\n")
        for s in range(nscenarios):
            author = sys.stdin.readline().split("\n")[0]
            number = erdos_number.get(author)
            if number == INFINITY:
                answer = author + " Infinity\n"
            else:
                answer = author + " " + repr(number) + "\n"
            sys.stdout.write(answer)

if __name__ == "__main__":
    main()