[理工] 103中央 演算法

看板Grad-ProbAsk作者 (boboL)時間5年前 (2020/12/10 19:51), 編輯推噓2(2推 0噓 13→)
留言15則, 3人參與, 5年前最新討論串1/1
https://imgur.com/jomcR7j
https://imgur.com/fAd1SvM
https://imgur.com/sefXczV
想請問大大們 第5題(1) 可以直接寫 用DFS從第1個開始跑, 當偵測到back edge時, 則代表有cycle 嗎? 第5題(2)(3)還有第7題 求指點 @д@ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.136.149.113 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1607601088.A.7B8.html
推
12/10 20:24, 5年前 , 1F
1 你解法很怪 這樣要額外先建link list再DFS
12/10 20:24, 1F
→
12/10 20:24, 5年前 , 2F
不是說不行
12/10 20:24, 2F
→
12/10 20:25, 5年前 , 3F
更直覺作法是直接disjoint set 每次撈一筆資料確認finds
12/10 20:25, 3F
→
12/10 20:25, 5年前 , 4F
et(u)!=findset(v)然後加進set C中 若findset(u)=findse
12/10 20:25, 4F
→
12/10 20:25, 5年前 , 5F
t(v)即有cycle
12/10 20:25, 5F
→
12/10 20:25, 5年前 , 6F
或input行數不等於n-1也會不構成Tree
12/10 20:25, 6F
→
12/10 20:28, 5年前 , 7F
更正是union 不是加進set C
12/10 20:28, 7F
→
12/10 20:58, 5年前 , 8F
a大 是這樣寫嗎?
12/10 20:58, 8F
推
12/10 21:11, 5年前 , 9F
(1)有back edge代表有cycle
12/10 21:11, 9F
→
12/10 21:45, 5年前 , 10F
(2)用greedy證明
12/10 21:45, 10F
→
12/10 22:44, 5年前 , 11F
是
12/10 22:44, 11F
→
12/11 00:22, 5年前 , 12F
m大 請問你怎用Greedy做,a大那能問你其他兩題嗎?
12/11 00:22, 12F
→
12/11 01:56, 5年前 , 13F
假如有個最好的選法不選edge(u,v)
12/11 01:56, 13F
→
12/11 01:59, 5年前 , 14F
你可以把matching給u的點 換成v 這樣就和最好的做法一樣
12/11 01:59, 14F
→
12/11 02:05, 5年前 , 15F
可以google "tree maximum matching"
12/11 02:05, 15F
‣ 更多 bobo1004 的文章
文章代碼(AID): #1VqWl0Uu (Grad-ProbAsk)