基本情報技術者 2010年 秋期 午前（科目A） 問06

親配列で表現された木の葉の数を求める問題【午前2 解説】

要点まとめ

• 結論: この親配列が表す木の葉は5個で、選択肢では ウ（5）が正解です。節点2,4,6,7,8が子を持たない葉になります。
• 根拠: A[i]が節点iの親番号を示すため、葉は配列Aの値（親番号）に一度も現れない節点番号で判定でき、表から該当節点を特定します。
• 差がつくポイント: 親番号の「出現有無」で葉を判定することと、A[i]=0の根が自動で葉とは限らない点（根も子を持たなければ葉）に注意すること。

正解の理由

よくある誤解

• 「A[i]=0 の節点は常に葉」という誤り：根が子を持たなければ葉になりますが、根が子を持っていれば葉ではありません。A[i]=0 はただ親がいないことを示します。
• 親の出現回数（頻度）で判断してしまう誤り：頻度（何人の子がいるか）ではなく「親として少なくとも1回出現するか否か」で葉を判定します。
• インデックスの取り違え：表が 1-indexed（節点番号が1から始まる）で与えられている点を忘れて 0-indexed として誤計算するミス。

解法ステップ

1. 配列Aの値を一通り見て、0以外の値（親番号）を集合parentsに追加する。
2. 節点番号全集合は {1,2,…,n}。葉は全集合からparentsを引いた差集合。
3. 葉の個数 = n - |parents|（ただしparentsは0を含めない）で求まる。計算量は O(n)。
   例（今回の表）: parents = {1,3,5} → 葉 = {1..8} \ {1,3,5} = {2,4,6,7,8} → 5個。

def count_leaves(A):
    # A は 1..n のインデックスを使う（A[1]..A[n]）、A[i]=0 は根
    n = len(A) - 1
    parents = set()
    for i in range(1, n+1):
        if A[i] != 0:
            parents.add(A[i])
    return n - len(parents)

# 今回の例
A = [None, 0,1,1,3,3,5,5,5]
print(count_leaves(A))  # 出力 5

選択肢別の誤答解説

• ア: 1 — 「根が1つだけで葉も1つ」と短絡する誤り。根が葉になるかは子の有無次第で、今回根は子を持つため不正解です。
• イ: 3 — 親の種類を数え間違えて3（親の種類 = 3）を葉数と混同する誤り。親の種類が3でも葉数は n - |parents| であり今回は5です。
• ウ: ウ — 正解（5）。親集合 {1,3,5} を除いた節点が葉で、節点2,4,6,7,8 の5個になります。
• エ: 7 — 多くの節点を葉と誤認して過大評価した値。実際には親として出現していない節点のみが葉です。

補足コラム

• 一般に「親配列」表現では、親として出現する節点を数えるだけで葉が判定できます。式で表すと葉の個数は $n-|\{A[i]\mid A[i]\ne 0\}|$ です。
• 木（根付き木）において全節点数を $n$、根以外の親参照の合計は $n-1$（各子は1つの親を持つ）ですが、親が重複するため「親としての種類数」は $1\le |\text{parents}|\le n-1$ となり、葉の数は場合によって変化します。
• 配列以外の表現（隣接リストなど）でも「子の数が0か否か」で葉を判定する点は同じです。

FAQ