貝殼找房第四題代碼，時間復雜度o(nlogn)
題目：
樣例：
代碼：
n = 4 # 結點數
pairs = [[1,2],[3,4],[3,1]] # 邊
child = [-1,2,0,1,0] # 孩子數 1-n 多加了個-1為了填充index=0
query = [[1,3],[4,1],[2,4]] # 查詢對
fa = list(range(0,n+1)) # 用來查找當前父親，與并查集相同， pre[i] = i 初始化
graph = [[0]*(n+1) for _ in range(n+1)] # 邊圖
for x1,x2 in pairs:
graph[x1][x2] = 1 # 把其變成無向圖
graph[x2][x1] = 1
sum1 = 0 # 用來判斷當前狀態
'''
這里每一次只找當前的孩子（child[i]==0）的結點，將其與之相連的點j，若還有孩子數，將其設為其父親，
并且將父親結點的孩子數child[j] -= 1，并將child[i] 設為-1，
如果所有結點為-1，即child和為-n，說明樹設定完成，sum1是用來判斷是否找完，
'''
while sum1 != -n:
sum1 = 0
for i in range(1,n+1):
if child[i] == 0:
for j in range(1,n+1):
if graph[i][j] == 1 and child[j] > 0:
fa[i] = j
child[j] -= 1
break # 只會有一個父親
child[i] = -1
sum1 += child[i]
'''
--------------------------------------分割線------------------------------------------
下面開始設定查詢步驟，
1、findpre 找到當前結點祖先的串列，并翻轉便于搜索
2、findnearpre 判斷兩點關系，
'''
def findpre(u):
fathers = []
while u != fa[u]:
fathers.append(fa[u])
u = fa[u]
fathers.reverse()
return fathers
def findnearpre(u, v):
u_list = findpre(u)
v_list = findpre(v)
if u in v_list:
return 'ZZZZ'
elif v in u_list:
return 'SSSS'
else:
# 查找最后相等的結點值
for i in range(0,min(len(u_list),len(v_list))):
if u_list[i] != v_list[i]:
return u_list[i-1]
else:
cur = u_list[i]
return cur
for u,v in query:
print(findnearpre(u,v))
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/1523.html
標籤：其他