I solved longest path in a tree problem using 2 BFS. I have tested my solution for many test cases including large amount of nodes. Solution seems to be giving correct answer very fast but I keep getting RUNTIME ERROR(NZEC).
Can anyone help me with finding what’s wrong with my solution ? Here’s my code:
from queue import Queue
class Tree:
def __init__(self):
self.nodes = {}
self.visited = {}
def addEdge(self, eFrom, eTo):
self.visited[eFrom] = 0
self.visited[eTo] = 0
if eFrom not in self.nodes.keys():
self.nodes[eFrom] = [eTo]
else:
self.nodes[eFrom].append(eTo)
if eTo not in self.nodes.keys():
self.nodes[eTo] = [eFrom]
else:
self.nodes[eTo].append(eFrom)
def bfsLP(self, startFrom):
q = Queue()
if not startFrom:
q.put(list(self.nodes.keys())[0])
else:
q.put(startFrom)
last = None
f = q.get()
self.visited[f] = 1
q.put(f)
while not q.empty():
bufor = q.get()
last = bufor
for f in self.nodes[bufor]:
if self.visited[f] == 0:
self.visited[f] = self.visited[bufor] + 1
q.put(f)
return [last, self.visited[last]]
def resetVisited(self):
for f in list(self.visited.keys()):
self.visited[f] = 0
edgesNumber = int(input())
x = Tree()
for i in range(edgesNumber):
a, b = [int(i) for i in input().split()]
x.addEdge(a, b)
answer1 = x.bfsLP(0)[0]
x.resetVisited()
answer2 = x.bfsLP(answer1)[1] - 1
print(answer2)