作者bobo1004 (boboL)
看板Grad-ProbAsk
標題[理工] 103中央 演算法
時間Thu Dec 10 19:51:26 2020
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1607601088.A.7B8.html
1F：推 aa871220: 1 你解法很怪 這樣要額外先建link list再DFS 12/10 20:24
2F：→ aa871220: 不是說不行 12/10 20:24
3F：→ aa871220: 更直覺作法是直接disjoint set 每次撈一筆資料確認finds 12/10 20:25
4F：→ aa871220: et(u)!=findset(v)然後加進set C中 若findset(u)=findse 12/10 20:25
5F：→ aa871220: t(v)即有cycle 12/10 20:25
6F：→ aa871220: 或input行數不等於n-1也會不構成Tree 12/10 20:25
7F：→ aa871220: 更正是union 不是加進set C 12/10 20:28
9F：推 mathtsai: (1)有back edge代表有cycle 12/10 21:11
10F：→ mathtsai: (2)用greedy證明 12/10 21:45
11F：→ aa871220: 是 12/10 22:44
12F：→ bobo1004: m大 請問你怎用Greedy做,a大那能問你其他兩題嗎? 12/11 00:22
13F：→ mathtsai: 假如有個最好的選法不選edge(u,v) 12/11 01:56
14F：→ mathtsai: 你可以把matching給u的點 換成v 這樣就和最好的做法一樣 12/11 01:59
15F：→ mathtsai: 可以google "tree maximum matching" 12/11 02:05