How to find LCA in a directed acyclic graph? Firstly, I am trying to understand the meaning of LCA in DAG. I read a definition somewhere-"Define the height of a vertex v in a DAG to be the length of the longest path from root to v. Among the vertices that are ancestors of both v and w, the one with the greatest height is an LCA of v and w."

In a graph like this 1->3 1->4 2->3 2->4, 3 and 4 will have multiple LCA's because the height of 1 and 2 would be same.

So, How can I proceed to implement this? I am thinking of applying the same approach that we used to find LCA in a binary tree by starting from root node (In this case, nodes having in_degree=0) but due to cross edges between the nodes this approach wouldn't work.eg. 1->2 1->3 3->2.

So, Is there some better way to find the LCA in DAG's?
Assume that you want to find the ancestors of x and y in a graph.

Maintain an array of vectors- parents (storing parents of each node).


Firstly do a bfs(keep storing parents of each vertex) and find all the ancestors of x (find parents of x and using parents, find all the ancestors of x) and store them in a vector. Also, store the depth of each parent in the vector.
Find the ancestors of y using same method and store them in another vector. Now, you have two vectors storing the ancestors of x and y respectively along with their depth.
LCA would be common ancestor with greatest depth. Depth is defined as longest distance from root(vertex with in_degree=0). Now, we can sort the vectors in decreasing order of their depths and find out the LCA. Using this method, we can even find multiple LCA's (if there).