least commom ancestor in general graph

[DJWS (...)]

我想要定義有向圖的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://www.ptt.cc/bbs/Prob_Solve/M.1483599077.A.AE0.html
推 FRAXIS: 是不是可以先找 SCC 然後建成 DAG 再來找 LCA?
→ DJWS: 可以呀  然後採用遞迴版DFS離開節點的逆序
→ DJWS: 這樣就有LCA的功效了  但是我沒看過類似的東西  想問有沒有
→ DJWS: 人看過
推 FRAXIS: 在 DAG 上找 LCA https://goo.gl/Uc6hhs
→ FRAXIS: 但是我覺得這跟你的問題還是不太一樣就是了..
推 ZanFu5566: Euler tour?
→ DJWS: 不太一樣  我想問的是圖上有環的LCA
推 aaaaajack: 我覺得點順序還是要符合拓樸排序才合理吧(同SCC內隨意)
→ aaaaajack: 不然假設x可到y但x比y大 y就直接被x吃掉了
→ DJWS: 遞迴版DFS離開節點的逆序 --> 一般圖的拓樸順序