我想要定義有向圖的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？
想請教板友是否看過類似的東西？

是不是可以先找 SCC 然後建成 DAG 再來找 LCA?

可以呀 然後採用遞迴版DFS離開節點的逆序這樣就有LCA的功效了 但是我沒看過類似的東西 想問有沒有人看過

在 DAG 上找 LCA https://goo.gl/Uc6hhs但是我覺得這跟你的問題還是不太一樣就是了..

Euler tour?

不太一樣 我想問的是圖上有環的LCA

我覺得點順序還是要符合拓樸排序才合理吧(同SCC內隨意)不然假設x可到y但x比y大 y就直接被x吃掉了

遞迴版DFS離開節點的逆序 --> 一般圖的拓樸順序