Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2017
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.28 KB | None | 0 0
  1. # python3
  2.  
  3. import sys, threading
  4. import queue
  5.  
  6. sys.setrecursionlimit(10**7) # max depth of recursion
  7. threading.stack_size(2**27) # new thread will get stack of such size
  8.  
  9. class Node:
  10. def __init__(self, index):
  11. self.index = index
  12. self.children = []
  13.  
  14. def addChild(self, child):
  15. self.children.append(child)
  16.  
  17. class TreeHeight:
  18. def read(self):
  19. self.n = int(sys.stdin.readline())
  20. self.parent = list(map(int, sys.stdin.readline().split()))
  21.  
  22. def compute_height(self):
  23. nodes = [Node(i) for i in range(self.n)]
  24. for i in range(self.n):
  25. if self.parent[i] == -1:
  26. self.root = nodes[i]
  27. else:
  28. nodes[self.parent[i]].addChild(nodes[i])
  29. q = queue.Queue()
  30. q.put(self.root)
  31. height = 0
  32. while(not q.empty()):
  33. size = q.qsize()
  34. if size > 0:
  35. height = height + 1
  36. for j in range(size):
  37. item = q.get()
  38. for i in item.children:
  39. q.put(i)
  40. return height
  41.  
  42.  
  43. def main():
  44. tree = TreeHeight()
  45. tree.read()
  46. print(tree.compute_height())
  47.  
  48. threading.Thread(target=main).start()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement