推 march20:這, WiiMonkey, 喔, 是 PsMonkey 大別生氣, 04/03 14:04
推 march20:暴米花網友似乎是新手, 我想他以後應該會知道的 XD 04/03 14:04
推 march20:找交集要花多少時間我是沒算過, 不過算 level + 找祖先是 04/03 14:06
推 march20:O(V+E) 的複雜度 04/03 14:06
推 march20:更精確一點, 是 Theta(V+E) 04/03 14:09
※ 引述《popcorn5368 (小宇)》之銘言：
: 在一個有分上下階層的類似樹狀的結構,且
: (1)此結構有cycle
: (2) 一個節點可屬於多個父節點
我覺得只要講第二條就可以了... 第一條講了反而混淆
: 求:給予多個節點,求這些節點的共同的祖先節點中,層級最低者
: 例: 如下圖,給予A,B,J,H,希望得到 X (結果應該有W及X,但X的層級最低)
:
: W Z
: -----------|---- |
: | | |
: | ----|----
: | | |
: | X Y
: | | |
: | ------------ --- --- ----
: | | | | |
: | | A K
: | | |
: | | B
: | | |
: | | ----|----
: | | | |
: | | C D
: H |
: | ----|----
: ---|--- | |
: | | E F
: I J
: 推 PsMonkey:麻煩請不要一直 cp 03/31 07:23
: 推 march20:你的 cycle 是指, 一直往父節點連最後會回到自己嗎? 03/31 07:32
: 推 march20:如果不是, 這種 case 似乎不適合叫 "cycle", 只能說 03/31 07:32
: 推 march20:不是 tree 03/31 07:33
: 推 march20:如果是這樣, 就先跑一遍決定出 level 03/31 07:34
: 推 march20:然後再用變形的"逆" bfs 找最小共同祖先 03/31 07:35
: 推 PsMonkey:重點是他怎麼建這個 structure，然後分辨上下吧 @_@ 03/31 09:46
: 推 popcorn5368:找level似乎是一個方法,但是因為有cycle 03/31 10:29
: → popcorn5368:有可能一個節點有多個level 03/31 10:30
你終究得要給每個 node 一個 level 吧？
不然你如何能說 node[x] 跟 node[y] 哪個層級高哪個層級低？
以你提的例子，H 跟 A 就得同個 level 不是嗎？
所以似乎版主大人的說法比較實際
（會不會比列出所有的 node 找交集快，我就沒去算了）
另外就是，如果有一個 node M，他的 parent 是 J 跟 E
那你預期得到的答案是啥？
: → popcorn5368:這個結構是有cycle的DAG(directed acyclic graph) 03/31 10:31
這句真的是... 亂七八糟
: → popcorn5368:抱歉喔...因為發文及轉錄後...很少人回,所以希望能獲넠 03/31 10:33
: → popcorn5368:得多點意見.....所以才..... 03/31 10:34
cp 就是 cp，沒啥好講的，Sysop 版一堆 cp 求情文章看了就煩
我壓根不懂你幹麼 po 去 Java 版
我還要聯絡好心的 qrtt1 把他的文章轉過來這裡統一彙整
: 推 ledia:DAG 就是沒有 cycle, 我想你的意思是, child 可以經不同 03/31 11:09
: → ledia:path 逆推回 共同的 parent ? 03/31 11:10
: 推 popcorn5368:是的,且一個節點可屬於多個父節點 03/31 11:19
--
侃侃長論鮮窒礙 首頁：http://www.psmonkey.idv.tw
眾目睽睽無心顫 Blog：http://ps-think.blogspot.com
煢居少聊常人事
殺頭容易告白難 歡迎參觀 Java 版（@ptt.cc）精華區 \囧/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.193.189