※ 引述《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