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?