[理工] 102中央資工ds&algo

[john2557 (Wanger)]

題目http://rapid.lib.ncu.edu.tw:8080/cexamn/exam/EC02_102_01.pdf

1.這題是要用下列的資料結構表示data
   所以像是array就一筆data的number      跟name分別佔兩個array的相同index位置？ 畫出來即可嗎？
那像是其他的資料結構呢?
Ex:double linked list要怎麼把兩個data fields放一個node?

4.求一個O(n)的algo去從加入一個邊到MST的新graph G'得到新的MST
原本的想法是找到加入此邊後形成的cycle C下手,刪掉weight最大的邊，但題目說找MST from scratch不得分
不太懂是什麼意思 該如何下手？

6.求一個O(n)的algo找最小size的uni length set
是用dp嗎？這題沒什麼想法

問題有點多 如果這幾題有會的版友麻煩解惑

手機排版請見諒


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 119.77.169.95
→ A4P8T6X9:6.用greedy即可，從邊界開始，每次取一個單位長度來cover
→ A4P8T6X9:。
→ A4P8T6X9:4.把新的邊放進原MST中，在對這個MST做DFS，因為只會有一
→ A4P8T6X9:個cycle，所以call到灰色，則從call到灰色的點開始往下
→ A4P8T6X9:到那個被call的灰色形成cycle，在找出最大的刪除即可。
→ A4P8T6X9:時間複雜度為O(n)因為只有n點，DFS，n次就可以跑完，找迴
→ A4P8T6X9:圈中最大的最多也是n次，所以O(n)。
→ A4P8T6X9:1.就直接放啊，一個node要放多少都可以啊。
推 bcza245682:可以借問第五題概念嗎XD
→ A4P8T6X9:1.如果有deg為1的點刪除還是連通，要是都沒deg1，則必有c
→ A4P8T6X9:ycle。刪除cycle中的點還是連通。
→ A4P8T6X9:2.先找deg1看看，沒有就用dfs找cycle。
→ A4P8T6X9:3.還是找cycle…
推 bcza245682:所以只找cycle的時間複雜度是O(|V|)嗎
→ john2557:感謝a大
→ A4P8T6X9:因為無向圖，找n個點就知道有沒有cycle啦。
→ A4P8T6X9:超過n次一定是call到重複的啊，簡單的鴿籠原理。
→ fright29:第一題還是不太懂 假如是放紅黑數的話 是直接拿123，234
→ fright29:345，233 直接比大小擺進去?
推 fright29:
→ A4P8T6X9:y