tags: APCS

c463－樹狀圖分析

題目連結： c463

題目解析

這題要求我們找出一個樹狀圖的根節點編號，並計算整個樹的總高度 H(T)。樹的根節點是沒有父節點的節點，而樹的總高度是所有節點高度的總和。

解題方向

1. 讀取資料：首先讀取樹的節點個數n，然後逐個讀取每個節點的子節點資訊。對於每個節點，先讀入其子節點的數量k，然後讀入k個子節點的編號。
2. 構建樹結構：利用鄰接表G來存儲樹的結構。G是一個列表的列表，其中G[i]包含了節點i的所有子節點。同時，使用Parent列表來記錄每個節點的父節點編號，初始值為 -1。
3. 尋找根節點：根節點是沒有父節點的節點，即Parent列表中值為 -1 的節點。
4. 計算樹的高度：透過深度優先搜索（DFS）遍歷樹，計算從每個節點到葉節點的最大距離，這個距離稱為節點的高度。函數dfs(node)遞迴地計算給定節點的高度，並更新全局height列表，其中height[i]表示節點i的高度。
5. 計算樹的高度和：樹的高度和（H(T)）是樹中所有節點的高度之和。遍歷height列表，將所有節點的高度累加得到總和。
6. 輸出結果：輸出根節點的編號（由於節點編號從1開始，而列表索引從0開始，因此輸出時需要加1）和樹的高度和。

程式解析

範例輸入：
7
0
2 6 7
2 1 4
0
2 3 2
0
0

1. 讀取節點個數 n = 7：這意味著樹狀圖有7個節點。
2. 初始化結構：
   • G = [ [] for i in range(n) ] 創建一個包含7個空列表的列表，用於存儲每個節點的子節點。
   • Parent = [ -1 for i in range(n) ] 創建一個長度為7的列表，初始值都為-1，用來記錄每個節點的父節點。
3. 構建樹結構：逐行讀取節點的子節點資訊。
   • 第1個節點：沒有子節點。
   • 第2個節點：有2個子節點，分別是節點6和節點7。因此，G[1] = [5, 6]（編號減1以符合Python索引）。
   • 第3個節點：有2個子節點，分別是節點1和節點4。因此，G[2] = [0, 3]。
   • 以此類推，直到所有節點的子節點資訊都被讀取和存儲。
4. 尋找根節點：在構建樹結構的過程中，對於每個子節點，都將其對應的父節點編號記錄在Parent列表中。最終，Parent列表中仍為-1的項目即為根節點。在這個例子中，假設最終找到的根節點為5（即列表中的編號4）。
5. DFS遞迴計算高度：從根節點開始進行深度優先搜索（DFS）。
   • 假設從節點5開始，dfs(5)被調用。由於節點5有2個子節點（節點3和節點2），因此會分別對這些子節點進行DFS遞迴調用，即dfs(3)和dfs(2)。
   • 在dfs(3)中，由於節點3沒有子節點，其高度設為0。返回後，繼續處理dfs(2)，依此類推。
6. 計算高度和：每次DFS調用返回時，都會更新當前節點的高度，並將其添加到高度和中。在這個例子中，如果節點5的兩個子節點的最大高度是3（假設），那麼節點5的高度就是4。
7. 輸出結果：
   • 根節點編號：5（根據步驟4中的發現）。
   • 高度和：對所有節點的高度進行加總。假設在這個例子中加總結果為4。

完整程式碼

#
# c463 樹狀圖分析 NA40%
# Part1 基本寫法 for DFS
# 不考慮 IO優化, 不考慮 DP
#

import sys
sys.setrecursionlimit(1000000)

def dfs(node):
    global height

    if len(G[node]) == 0:
        height[node] = 0
        return 0

    else:
        mx = 0
        for i in G[node]:
            dfs(i)
            # 同一個 node 在不同 dfs 下哪個高度比較高
            # 最後更新回 height list
            mx = max(mx, height[i]+1)

        height[node] = mx


# start
n = int(input())

G = [ [] for i in range(n) ] # 創造 graph 的結構
Parent = [ -1 for i in range(n) ]


for i in range(n):
    row = list(map(int, input().split()))

    if row[0]>0:
        # 取出第一個之後的元素（因為第一個數代表有幾個子節點，後面的數字才是節點值）
        t = []
        for x in range(1, len(row)):
            t.append(row[x]-1)
            #  是將子節點的編號轉換為0基的索引（因為在Python中，清單索引從0開始）

        G[i] = t

        for j in G[i]:
            Parent[j] = i # 指派父節點

# 尋找 Parent list 中, 仍然是 -1 的為 root
for r in range(n):
    if Parent[r] == -1:
        root = r
        break

height = [ 0 for x in range(n) ]

# 由根開始探索
dfs(root)

ans = 0
for x in range(n):
    ans += height[x]

print(root+1)
print(ans)

AC版詳解