Skip to content

Instantly share code, notes, and snippets.

@evansb
Created July 4, 2014 16:21
Show Gist options
  • Save evansb/97b18b2ed7bb037113d5 to your computer and use it in GitHub Desktop.
Save evansb/97b18b2ed7bb037113d5 to your computer and use it in GitHub Desktop.
Erdos Number (UVA 10044).
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment