Статья Автор: Ратькин Иван

5

from collections import deque
def BFS(g,s):
    visited=[False]*n
    tm=[0]*n
    visited[s]=True
    queue=deque([s])
    while queue:
        v=queue.popleft()
        for nxt in sorted(g[v]):
            if not visited[nxt]:
                visited[nxt]=True
                queue.append(nxt)
                tm[nxt]=tm[v]+1
    ma=max(tm)
    v=tm.index(ma)
    return v,max(tm)
n=int(input())
g=list([] for _ in range(n))
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
v1,_=BFS(g,0)
_,ma=BFS(g,v1)
print(ma+1)
Загрузка...
Чтобы оставить комментарий, необходимо авторизоваться
💬
Пока нет комментариев. Будьте первым!
Печать