APCS 考古題 Tree Analysis

APCS.2017.10.28考古題下載

※簡單方法(效能稍差)：

※其它方法(效能較佳)：(時間複雜度較小)

想法：
Step1.將樹葉節點納入待拜訪的佇列 (queue)

Step2.逐一由佇列中取出節點並拜訪各自的父節點並更新該父節點高度值

Step3.一旦被處理的父節點之子節點皆被拜訪過後，將該父節點也塞入待拜訪佇列的尾端

Step4.重複 Step2~3 直到拜訪到根節點為止

import queue
In = input().strip()
while In!="":# while not In    
    n= int(In)
    p=[-1]*(n+1)  #p[i]=j，表示i的雙親為j    
    d=[0]*(n+1)   #紀錄節點深度
    num=[0]*(n+1) #紀錄節點的子節點個數，子節點計算過後就減1
    t =queue.Queue()  #儲存待走訪之節點
    for i in range(1,n+1): #為方便觀察從索引 1 開始放置元素
        #line = list(map(int,f.readline().split()) )
        line = list(map(int,input().split()) ) #讀入一行後轉換為 int
        k = line[0]
        num[i] = k #節點 i 的子節點個數
        if k == 0:
            t.put(i) #葉節點先納入待走訪的節點
        else:
            for j in line[1:]:
                p[j] = i   #使用陣列p紀錄 j 的parent為i
    i = 0
    node = 0
    while True:
        node = t.get() #取出待走訪之節點
        if p[node] == -1:break #沒有父節點代表它是根節點==>結束迴圈
        d[p[node]]=max(d[p[node]],d[node]+1) #葉節點深度+1 和 已記錄之深度取大者作為本節點深度
        num[p[node]]=num[p[node]]-1 #父節點底下未走謗過的子節點數目減1 
        if num[p[node]] == 0: #當所有子節點都走訪過時，將該父節點納入待走訪之節點
            t.put(p[node])
        
    print(node)#最後一個從t取出的就是根節點
    print(sum(d))#最後一個從t取出的就是根節點
    try:In = input().strip()
    except EOFError:break