作者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/cn.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