# 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?

• Not every two vertices have a least common ancestor. If you interpret your DAG as a poset (by taking transitive closure), then least common ancestor corresponds to meet ($\land$). A poset in which every two elements have a meet is called a meet-semilattice. Not every poset is one. – Yuval Filmus Apr 2 '18 at 11:51
• "for a graph like this 1->2 1->3 3->2, the LCA would be 3 and not 1" -- the LCA of what? – j_random_hacker May 18 '18 at 7:57
• I have updated my question – shiwang May 18 '18 at 8:08