[理工] 103中央 演算法

[bobo1004 (boboL)]

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
推 aa871220: 1 你解法很怪 這樣要額外先建link list再DFS
→ aa871220: 不是說不行
→ aa871220: 更直覺作法是直接disjoint set 每次撈一筆資料確認finds
→ aa871220: et(u)!=findset(v)然後加進set C中 若findset(u)=findse
→ aa871220: t(v)即有cycle
→ aa871220: 或input行數不等於n-1也會不構成Tree
→ aa871220: 更正是union 不是加進set C
→ bobo1004: https://imgur.com/9LyPuFB a大 是這樣寫嗎?
推 mathtsai: (1)有back edge代表有cycle
→ mathtsai: (2)用greedy證明
→ aa871220: 是
→ bobo1004: m大 請問你怎用Greedy做,a大那能問你其他兩題嗎?
→ mathtsai: 假如有個最好的選法不選edge(u,v)
→ mathtsai: 你可以把matching給u的點 換成v 這樣就和最好的做法一樣
→ mathtsai: 可以google "tree maximum matching"