[理工] 103中央演算法 bobo1004 PTT批踢踢實業坊

[理工] 103中央演算法

作者: bobo1004 (boboL) 2020-12-10 19:51:26

https://imgur.com/jomcR7j
https://imgur.com/fAd1SvM
https://imgur.com/sefXczV
想請問大大們
第5題(1) 可以直接寫用DFS從第1個開始跑, 當偵測到back edge時, 則代表有cycle 嗎?
第5題(2)(3)還有第7題求指點 @д@

作者: aa871220 (TMVP_Yueko) 2020-12-10 20:24:00

1 你解法很怪這樣要額外先建link list再DFS不是說不行更直覺作法是直接disjoint set 每次撈一筆資料確認findset(u)!=findset(v)然後加進set C中若findset(u)=findset(v)即有cycle或input行數不等於n-1也會不構成Tree更正是union 不是加進set C

作者: bobo1004 (boboL) 2020-12-10 20:58:00

https://imgur.com/9LyPuFB a大是這樣寫嗎?

作者: mathtsai (mathtsai) 2020-12-10 21:11:00

(1)有back edge代表有cycle(2)用greedy證明

作者: aa871220 (TMVP_Yueko) 2020-12-10 22:44:00

是

作者: bobo1004 (boboL) 2020-12-11 00:22:00

m大請問你怎用Greedy做,a大那能問你其他兩題嗎?

作者: mathtsai (mathtsai) 2020-12-11 01:56:00

假如有個最好的選法不選edge(u,v)你可以把matching給u的點換成v 這樣就和最好的做法一樣可以google "tree maximum matching"

繼續閱讀

[理工] 100 交大 Floyd-Warshall 負weight cyclebooowei1203 [理工] 線代函數唯一性aa871220 [理工] 107台大電機離散（6）（11）jimmylin1024 [理工] 計組（下）p.175sososlee [理工] 108 台大電機丙複選題joywilliamjo [理工] 線代 rank相關 109清大數學ff00662299 [理工] 考古題作業系統Race condition LaLaplace [理工] 106 台大電機丙資結joywilliamjo [理工] 離散成大108數學try66889 [理工] 108 交大資演 reductionaa871220

[理工] 103中央 演算法

[理工] 103中央演算法