發表新討論
#17895: 判斷樹


freedom501999@gmail.com (帥氣魔方生)

b517. 是否為樹-商競103 -- 103學年度 商業類程式設計競賽 模擬題 | From: [39.8.203.54] | 發表日期: 2019-05-30 20:02

判斷是否為樹，有以下兩個條件

1. 頂點數 = 邊數 + 1 ，如果此條件不成立，直接輸出 F，不用跑 DFS

2. 以一個頂點開始，跑一次DFS，如果所有頂點都拜訪過一次，代表是一顆樹，反之若存在一頂點沒拜訪，就不是樹

#31120: Re: 判斷樹


aa0982590040@gmail.com (kk_andy)

b517. 是否為樹-商競103 -- 103學年度 商業類程式設計競賽 模擬題 | From: [36.229.178.224] | 發表日期: 2022-07-13 09:05

判斷是否為樹，有以下兩個條件

1. 頂點數 = 邊數 + 1 ，如果此條件不成立，直接輸出 F，不用跑 DFS

2. 以一個頂點開始，跑一次DFS，如果所有頂點都拜訪過一次，代表是一顆樹，反之若存在一頂點沒拜訪，就不是樹


寫dfs太麻煩了
只接一開始用集合的方式就可以了
會寫比較短

ZeroJudge Forum