问个朱刘算法的问题.....
tjuacm吧
全部回复
仅看楼主
level 4
发烧的巧克力 楼主
对于不定根的有向图最小生成树，要找到真实根的话只要记录最后被选中的 起点是虚拟根的那条边的终点就好了。但是如果需要把所有被选中的边输出的话该怎么解决呢。。。虽然还没见过这么恶心的题目。。。
2013年08月05日 10点08分 1
level 7
txshs123
你的问题是指ZL算法最后输出具体的解的情况？
2013年08月05日 10点08分 2
level 7
txshs123
最小树形图肯定是有根的啊，而且只有一个。
ZL算法是可以知道解的，prev[]数组就是每个节点的父亲，拿prev[i]到i就是一条边。
2013年08月05日 10点08分 3
发烧的巧克力
回复 发烧的巧克力 :pre[i]到i记录的是每一次寻找生成树时所得到的边，但是那些边的起点和终点都可能是个缩点吧。。.怎么把那个缩点再打开呢。。
2013年08月05日 10点08分
txshs123
回复 发烧的巧克力 :如果prev[i]就是一个单独的点，那prev[i]->i就是答案里的一条边，否则，循环(可能需要迭代，因为可能缩了多次)构成prev[i]的点集，看边长的关系即可，具体的有点忘了的，但这样复杂度肯定没问题，暴力点没事，朱刘算法本身就是EV的复杂度，很暴力的。
2013年08月05日 14点08分
发烧的巧克力
回复 txshs123 :好的，大概明白了，谢单大牛~~
2013年08月06日 01点08分
txshs123
回复 发烧的巧克力 :不客气，我也正好复习了一遍。
2013年08月06日 01点08分
1