#37977: python 紀錄 WA70%


BensonDC (python戰士)

學校 : 不指定學校
編號 : 240921
來源 : [163.32.78.214]
最後登入時間 :
2024-11-06 14:27:58
b967. 4. 血緣關係 -- 2016年3月apcs | From: [1.175.194.6] | 發表日期 : 2023-10-21 21:24

"""
首先創造一個無向鄰接表,接著做2次BFS
先對於任意一點做BFS,求得離該點最遠的點
接著在從那個最遠的點做BFS,求出來的長度即為直徑
"""
from collections import deque
while True:
    try:
        n=int(input())
        L=[[] for _ in range(n)]
        for _ in range(n-1):
            p,c=map(int,input().split())
            L[p].append(c)
            L[c].append(p)
    except:
        break
    flag=[False]*(n)
    queue=deque()
    queue.append((0,0))
    res=[0]
    flag[0]=True
    while queue:
        node,count=queue.popleft()
        for i in L[node]:
            if not flag[i]:
                res.append(i)
                queue.append((i,count+1))
                flag[i]=True
    flag=[False]*(n)
    queue.append((res[-1],0))
    flag[res[-1]]=True
    res=0
    while queue:
        node,count=queue.popleft()
        for i in L[node]:
            if not flag[i]:
                queue.append((i,count+1))
                res=max(res,count+1)
                flag[i]=True
    print(res)
    
    
        

 
ZeroJudge Forum