Splitting a Directed Acyclic Graph (DAG) into components, then finding root and last child in those components

Question

I want to split a graph into its components (like in the example DAG below. Note the colored identifiers of each node as they represent the components). After I've found the components in the picture I want to find the root and last child of that component. Take the blue component for example, the root is E and the last child is H. Green: root B - last child H.

Example graph:

If you can find a connection between E-H, B- E, B-H, A-I without splitting it into components. Let me know, as that is my final goal.

About the compiling of components. That is actually my final goal. I just wanted to include that to maybe get you a better understanding of what I'm trying to achieve. This can be don't once I find these connections.

Questions I found helpful but not answered my question:

• Algorithm to find lowest common ancestor in directed acyclic graph?

• Finding best common ancestor of two leaf nodes where nodes have zero, one, or two parents

(These answers might be sufficient but I don't know how to implement it)

Note:

• Please post all example code in C++ or C# (if you're going to post example code)

• This is my first question. If I've done something wrong please let me know.

// Big edit: Reworked the question to make it more clear what I want. Introduced components as I might think that will be more helpful.

Answer 1

Too long for a comment but I don't think you are finding all the common ancestors:

From wikipedia:

In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).

If you consider the LCA of the parents then there are 4 parents of vertex H which are C, D, F and G then you can consider the LCA to be the values for any pair of parents:

• LCA( C, D ) = B
• LCA( C, F ) = C
• LCA( C, G ) = C
• LCA( D, F ) = D
• LCA( D, G ) = D
• LCA( F, G ) = E

so, the LCAs of the parents of H are B, C, D and E.

The common ancestors will be the lowest common ancestor(s) and their ancestors - so A, B, C, D and E.

You need to address why A, C and D are being excluded as common ancestors.