發表新討論
#30161: 較快的作法 葉節點到根節點


wer12369qaz15963@gmail.com (dentr)

學校 : 新北市立清水高中
編號 : 174903
來源 : [134.208.49.24]
最後登入時間 ：
2024-11-21 18:28:16
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [219.84.98.239] | 發表日期 : 2022-05-02 14:48

相比 DFS 每個節點取深度 這題用這個方法更快

葉節點越多越慢

如果你是寫 python 或 Java  或者你想要這題更快的話 可以用這個做法

在測資時 把沒有子節點的節點紀錄下來 因為我們要從葉節點開始往上讀

以每個葉節點往上讀過各一遍 取H的最大值

例:

                7

            /

         2

      /     \

 3             4

                    \ 

                       5

以這個圖來說 當我從3開始走時 2的高度是1 當我以5開始走時 2的高度是2 要取最大值 所以 2的高度是2

所有葉節點的終點即為根節點 第一部分解決

把 所有高度總和 第二部份解決 

注意: 這題要迴圈 用遞迴 會因為呼叫太多次而錯誤

 

 
#33401: Re: 較快的作法 葉節點到根節點


illumeow0223@gmail.com (幻喵)

學校 : 臺北市立建國高級中學
編號 : 219078
來源 : [27.51.82.35]
最後登入時間 ：
2024-01-30 09:39:35
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [210.71.78.245] | 發表日期 : 2023-01-03 10:20

相比 DFS 每個節點取深度 這題用這個方法更快

葉節點越多越慢

如果你是寫 python 或 Java  或者你想要這題更快的話 可以用這個做法

在測資時 把沒有子節點的節點紀錄下來 因為我們要從葉節點開始往上讀

以每個葉節點往上讀過各一遍 取H的最大值

例:

                7

            /

         2

      /     \

 3             4

                    \ 

                       5

以這個圖來說 當我從3開始走時 2的高度是1 當我以5開始走時 2的高度是2 要取最大值 所以 2的高度是2

所有葉節點的終點即為根節點 第一部分解決

把 所有高度總和 第二部份解決 

注意: 這題要迴圈 用遞迴 會因為呼叫太多次而錯誤

 


我用這個方法寫
但8就TLE了
有人可以指出我哪裡多迴了嗎
還是說有更好的寫法?

node_num = int(input())

tree = [0 for _ in range(node_num)]
leaves = []
for i in range(node_num):
    temp = [int(n) for n in input().split()]
    if temp[0] == 0:    leaves.append(i+1)
    else:  
        for j in temp[1:]:  tree[j-1] = i+1
#print(tree)
#print(leaves)
root = tree.index(0)+1
print(root)

height = [0 for _ in range(node_num)]
for leaf in leaves:
    current_node = leaf
    h = 1
    while current_node != root:
        current_node = tree[current_node-1]
        height[current_node-1] = max(h, height[current_node-1])
        h += 1
print(sum(height))
 
#38374: Re: 較快的作法 葉節點到根節點


linawa015@gmail.com (小林)

學校 : 不指定學校
編號 : 199044
來源 : [203.72.100.115]
最後登入時間 ：
2023-11-24 14:50:18
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [203.72.100.115] | 發表日期 : 2023-11-16 11:33

相比 DFS 每個節點取深度 這題用這個方法更快

葉節點越多越慢

如果你是寫 python 或 Java  或者你想要這題更快的話 可以用這個做法

在測資時 把沒有子節點的節點紀錄下來 因為我們要從葉節點開始往上讀

以每個葉節點往上讀過各一遍 取H的最大值

例:

                7

            /

         2

      /     \

 3             4

                    \ 

                       5

以這個圖來說 當我從3開始走時 2的高度是1 當我以5開始走時 2的高度是2 要取最大值 所以 2的高度是2

所有葉節點的終點即為根節點 第一部分解決

把 所有高度總和 第二部份解決 

注意: 這題要迴圈 用遞迴 會因為呼叫太多次而錯誤

 


我用這個方法寫
但8就TLE了
有人可以指出我哪裡多迴了嗎
還是說有更好的寫法?

node_num = int(input())

tree = [0 for _ in range(node_num)]
leaves = []
for i in range(node_num):
    temp = [int(n) for n in input().split()]
    if temp[0] == 0:    leaves.append(i+1)
    else:  
        for j in temp[1:]:  tree[j-1] = i+1
#print(tree)
#print(leaves)
root = tree.index(0)+1
print(root)

height = [0 for _ in range(node_num)]
for leaf in leaves:
    current_node = leaf
    h = 1
    while current_node != root:
        current_node = tree[current_node-1]
        height[current_node-1] = max(h, height[current_node-1])
        h += 1
print(sum(height))

我把leaves改成set

可以避免父節點有多個同樣高度子節點的情況

from sys import stdin
import collections as coll
graph_reversed=coll.defaultdict(int)
n=int(stdin.readline())
height=[0 for i in range(n+1)]
leaf=set([])
# 儲存(節點，高度)
for i in range(1,n+1):
    num,*child=map(int,stdin.readline().split())
    if num==0:
        leaf.add((i,0))
    for c in child:
        graph_reversed[c]=i
head=0
while leaf:
    x,h=leaf.pop()
    height[x]=max(height[x],h)
    if height[x]+1>height[graph_reversed[x]] and graph_reversed[x]:
        leaf.add((graph_reversed[x],height[x]+1))
    if not graph_reversed[x]:
        head=x
print(head)
print(sum(height))
 
ZeroJudge Forum