daily pastebin goal
34%
SHARE
TWEET

Untitled

a guest May 16th, 2018 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import numpy as np
  2. import collections
  3.  
  4. graph = {}
  5. size = int(raw_input())
  6.  
  7. for i in range(size-1):
  8.     inp = raw_input()
  9.     if not inp: break
  10.     [down, up] = inp.split(' ')
  11.     if (graph.get(up) is None):
  12.         graph[up] = []
  13.     if (graph.get(down) is None):
  14.         graph[down] = []
  15.     current = graph.get(up)
  16.     current.append(down)
  17.     graph[up] = current
  18.  
  19. def breadth_first_search(graph, root):
  20.     level = 1
  21.     human_level = {}
  22.     last_level = 1
  23.     visited, queue = set(), collections.deque([root])
  24.     while queue:
  25.         vertex = queue.popleft()
  26.         for neighbour in graph[vertex]:
  27.             if neighbour not in visited:
  28.                 if (last_level > level):
  29.                     level += 1
  30.                 visited.add(neighbour)
  31.                 queue.append(neighbour)
  32.                 human_level[neighbour] = level
  33.                 last_level = level
  34.         last_level += 1
  35.     return human_level
  36.  
  37. human_level = breadth_first_search(graph, 'X')
  38. human_level['X'] = 0
  39.  
  40. for human in sorted(human_level):
  41.     print(str(human) + ' ' + str(human_level[human]))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top