我想要定义有向图的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离开节点的逆序 --> 一般图的拓朴顺序