a584: 2. 親等關係
Tags :
Accepted rate : 95人/101人 ( 94% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-27 21:10

Content
  社會老師在小明的班上請同學們討論法律上的一等親二等親三等親如何區分與計算,並於下一堂課進行報告。小明在網路上找到一個計算親等的建議方式--畫樹狀圖,圖中每一個節點代表一個人名,該節點的父節點則存放他父親的名字,而該節點的子節點則存放他的小孩的名字。在樹狀圖中二個親屬之間需經幾條的連結(link)才能連接就是幾等親。例如下圖中,LIZ 和他的父親 BOB 之間只需經過一條連結,所以是一等親,而 LIZ 和他的爺爺 PAM 就需經過二條連結,是二等親。另外,LIZ 需經過四條連結才能與和 JIM 相連,所以就是四等親了。你能寫一個程式自動判斷二個人之間的親等關係嗎?
  為了簡化問題,我們做了以下限制:
  1. 我們以父親的名字來代表父母親雙方,且以祖父的名字來代表祖父母雙方。
  2. 每一個節點會有多少個子節點視存入該節點的人名有多少個親生子女而定,但最多不會超過十個。
Input
  輸入包含了 n+2 行 (1 ≤ n ≤ 50),第一行輸入只有一個 n 值,表示共有 n 筆資料以供建立樹狀圖。第 2 行至第 n+1 行則分別輸入 n 筆資料,每筆資料中,第一個英文名字為某一節點的名字,其後的英文名字為該節點之子節點的名字,每個名字之間以空白隔開,各筆資料之間沒有前後順序關係,但一定可以建出一樹狀圖。最後一行輸入則是要判斷親等關係的二個不同人的名字 (該名字一定會出現在輸入之資料中),名字之間亦以空白隔開。在輸入資料中,所有的英文名字都以 3 個大寫英文字母命名。
Output
  請輸出一個數字,代表該二人間的親等關係。
Sample Input
輸入範例一
3
PAM BOB TOM PAT
BOB LIZ ANN
PAT JIM
LIZ TOM

輸入範例二
2
BOB LIZ ANN
PAM BOB TOM
LIZ ANN
Sample Output
輸出範例一
3

輸出範例二
2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
出處:
101學年度北基區資訊學科能力競賽 [管理者:
pcshic (PCSHIC)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」