※ 引述《UesugiKura (上杉倉)》之銘言： : 在下今年要參加全國高職商科技藝競賽 : 小的不才 其中有一道模擬試題一直不能想通怎麼去寫 : 題目如下: : ---------------------------------------------------- : 寫一個程式，讀入一圖形的資料，然後回答該圖是否為樹。 : 輸入說明： : 第一列的數字n代表有幾組資料要測試，而n的值介於1和10之間。 : 第二列以後則是每一組測試資料。每組測試資料代表一圖形，內容為邊的資料。 : 每個邊以2個整數i,j表示，0<=i,j<=30，此2整數為節點的編號， : 代表從i節點和j節點有邊相連。 : 0,0這個邊代表此組輸入資料結束。 : 輸出說明： : 每組測試資料輸出一列，輸出每組測試資料以及該組測試資料是否為樹。 : T為樹，F不為樹。（輸出均為大寫） : 輸入檔案1：【檔名：in1.txt】 : 5 ...... : 3,8 6,8 6,4 5,3 5,6 8,2 2,0 0,0 樹的規則你講了一半，而重點是任二點之間「只有」一條路徑. 一方面要找迴路,另一方面要判斷整個圖是一個,沒有切分成二部份. 如果找到是以上二種情況,就不是樹. 前者,找迴路,作法基本是像以下這樣: 找5到6之間有沒有迴路,先從5開始建一個樹, 第一層 第二層 第三層 5 - { 8, 4, 6 } - {{3,6,2}, 6, {8,4}} - 第四層 { {{5, {4,5}, 0}, {8,5}, {{3,2}, {}} } 每一層產生的原則,大概是看它上一層以及上上一層的關係,例如,第四層最後找到{}, 是由第三層的最右邊節點4, "尋找與4相鄰的節點,但扣掉4上一層節點6" 這樣. 說是樹,其實為了程式好做,是抄寫成好幾列: 5, 8, 3, 5, ... 5, 8, 6, 4, ... 5, 8, 6, 5, ... 5, 8, 2, 0, ... 5, 4, 6, 8, ... 5, 4, 6, 5, ... 5, 6, 8, 3, ... 5, 6, 8, 2, ... 5, 6, 4 每一列查過去,會發現 5,8,3,5,... 和 5,4,6,5,... 是迴路. 至於第二個判斷,判斷任二點之間是否沒有連通 (以決定圖是否為一個完整單元), 不曉得是不是把圖結構做出來,並在裡頭走訪,看看如果全都走到盡頭卻碰不到目標, 則斷定圖型不是一個完整單元. --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.167.50.25 ※ 編輯: yauhh 來自: 118.167.50.25 (11/27 01:00)