#34697: 如何節省更多時間?
s11104220@school.saihs.edu.tw
(施同學)
學校
:
臺北市立松山高級工農職業學校
編號 : 221254
來源 : [118.165.27.136]
最後登入時間 ：
2024-08-27 03:46:40
n=int(input())
a=[]
nhead=[]#not head
for i in range(n):
a.append(list(map(int,input().split())))
del a[i][0]#不需要
nhead.extend(a[i])#不可能是head的數字
head=(1+n)*n//2-sum(nhead)#等差級數 如果nhead=[1,3] (1+2+3)-(1+3)=head=2
print(head)
#建立反向樹狀圖(BFS)
rb=[None for _ in range(n)]#使用父節點->子節點 建立子節點->父節點
tasks=[head-1]
while True:
sa=a[tasks[0]]#節省時間變數
for i in range(len(sa)):
sai1=sa[i]-1#節省時間變數
rb[sai1]=tasks[0]
tasks.append(sai1)
del tasks[0]
if tasks==[]:break
#葉節點搜尋
h=[0 for _ in range(n)]
for i in range(n):
if a[i]!=[]:continue
deep=1
ptr=i
ptr=rb[ptr]
while True:
rbp=rb[ptr]#節省時間變數
if h[ptr]<deep:h[ptr]=deep#比深度
else:break#有更深的已經搜尋過了
if rbp==None:break
ptr=rbp
deep+=1
print(sum(h))
ZeroJudge Forum