Tree Diameter For Each Testcase
Programming Interview
Hard
5 views
Problem Description
For each testcase you get a tree with n nodes. Output the diameter length (number of edges on longest path).
Input Format
First integer t. For each: n then n-1 edges u v (1-based).
Output Format
t lines diameter length.
Sample Test Case
Input:
1
5
1 2
2 3
3 4
2 5
Constraints
Sum of n over all testcases
Official Solution
import sys
from collections import deque
p=sys.stdin.read().strip().split()
if not p:
sys.exit(0)
it=iter(p)
t=int(next(it))
out=[]
def bfs(start,g):
n=len(g)-1
dist=[-1]*(n+1)
q=deque([start])
dist[start]=0
far=start
while q:
u=q.popleft()
if dist[u]>dist[far]:
far=u
for v in g[u]:
if dist[v]==-1:
dist[v]=dist[u]+1
q.append(v)
return far,dist[far]
for _ in range(t):
n=int(next(it))
g=[[] for _ in range(n+1)]
for i in range(n-1):
u=int(next(it)); v=int(next(it))
g[u].append(v)
g[v].append(u)
a,_d=bfs(1,g)
b,d=bfs(a,g)
out.append(str(d))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!