作者DJWS (...)
看板Prob_Solve
标题least commom ancestor in general graph
时间Thu Jan 5 14:51:14 2017
我想要定义有向图的LCA G = (V,E)
1. 将图上每一点定序，给予编号1到V
2. 一个点的父亲，定义为入边的另一个端点 fa(x) = {for all p: (p,x) in E}
3. 一个点的祖先，定义成父亲0次至无限多次 anc(x) = {x, fa(x), fa(fa(x)), ...}
4. 两个点的LCA，定义成两家祖先的交集当中序号最大者 i
是不是就能定义有向图的LCA？
想请教板友是否看过类似的东西？
--
最近发现dominator tree的演算法
似乎可以用一般图的LCA来解释
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.137.7.138
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1483599077.A.AE0.html
1F：推 FRAXIS: 是不是可以先找 SCC 然後建成 DAG 再来找 LCA? 01/05 23:13
2F：→ DJWS: 可以呀 然後采用递回版DFS离开节点的逆序 01/06 07:27
3F：→ DJWS: 这样就有LCA的功效了 但是我没看过类似的东西 想问有没有 01/06 07:29
4F：→ DJWS: 人看过 01/06 07:29
6F：→ FRAXIS: 但是我觉得这跟你的问题还是不太一样就是了.. 01/06 11:56
7F：推 ZanFu5566: Euler tour? 01/06 13:42
8F：→ DJWS: 不太一样 我想问的是图上有环的LCA 01/06 17:10
9F：推 aaaaajack: 我觉得点顺序还是要符合拓朴排序才合理吧(同SCC内随意) 01/09 15:32
10F：→ aaaaajack: 不然假设x可到y但x比y大 y就直接被x吃掉了 01/09 15:33
11F：→ DJWS: 递回版DFS离开节点的逆序 --> 一般图的拓朴顺序 01/09 19:42